## Abstract

Given a collection of weighted sets, each containing at most k elements drawn from a finite base set, the k-set packing problem is to find a maximum weight sub-collection of disjoint sets. A greedy algorithm for this problem approximates it to within a factor of k, and a natural local search has been shown to approximate it to within a factor of roughly k - 1. However, neither paradigm can yield approximations that improve on this. We present an approximation algorithm for the weighted k-set packing problem that combines the two paradigms by starting with an initial greedy solution and then repeatedly choosing the best possible local improvement. The algorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotically tight. This is the first asymptotic improvement over the straightforward ratio of k.

Original language | English |
---|---|

Pages (from-to) | 223-240 |

Number of pages | 18 |

Journal | Journal of Algorithms |

Volume | 39 |

Issue number | 2 |

DOIs | |

Publication status | Published - May 2001 |

## Other keywords

- Approximation algorithms
- Greedy algorithms
- Local search
- Set packing
- Weighted independent set