We study algorithms based on local improvements for the k-Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver has been improved by Sviridenko and Ward from k/2 + ∈ to k+2/3, and by Cygan to k+1/3 + ∈ for any ∈ ＞ 0. In this paper, we achieve the approximation ratio (k+1)/3 + ∈ for the k-Set Packing problem using a simple polynomial-time algorithm based on the method by Sviridenko and Ward. With the same approximation guarantee, our algorithm runs in time singly exponential in 1/∈~2, while the running time of Cygan's algorithm is doubly exponential in 1/∈. On the other hand, we construct an instance with locality gap k+1/3 for any algorithm using local improvements of size O(n~(1/5)), where n is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.
展开▼
