Greedy local improvement and weighted set packing approximation

Barun Chandra
Department of Computer Science, New Haven University, USA

 Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

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 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.