Barun ChandraGiven 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 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.
Department of Computer Science, New Haven University, USA
Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.
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.