Approximate the k-Set Packing Problem by Local Improvements

Abstract

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 $\frac{k}{2}+\epsilon$ to $\frac{k+2}{3}$, and by Cygan to $\frac{k+1}{3}+\epsilon$ for any $\epsilon >0$. In this paper, we achieve the approximation ratio $\frac{k+1}{3}+\epsilon$ 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 $\frac{1}{{\epsilon }^2}$, while the running time of Cygan's algorithm is doubly exponential in $\frac{1}{\epsilon }$. On the other hand, we construct an instance with locality gap $\frac{k+1}{3}$ for any algorithm using local improvements of size $O(n^{1/5})$, here $n$ is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.

14 pages, 2 figures

References in corpus (2)

• Improved approximation for 3-dimensional matching via bounded pathwidth local search
• Large Neighborhood Local Search for the Maximum Set Packing Problem

Cited by in corpus (1)

• Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries