Greedy local improvement and weighted set packing approximation

Given a collection of weighted sets, each containing at most k elements dra wn from a finite base set, the k-set packing problem is to find a maximum w eight 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 bee n shown to approximate it to within a factor of roughly k - 1. However, nei ther paradigm can yield approximations that improve on this. We present an approximation algorithm for the weighted k-set packing proble m that combines the two paradigms by starting with an initial greedy soluti on and then repeatedly choosing the best possible local improvement. The al gorithm has a performance ratio of 2(k + 1)/3, which we show is asymptotica lly tight. This is the first asymptotic improvement over the straightforwar d ratio of k. (C) 2001 Academic Press.