Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search

摘要

One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pair wise disjoint sets. A special case of 3-Set Packing is the well known 3-Dimensional Matching problem, which is a maximum hyper matching problem in 3-uniform tripartite hyper graphs. Both problems belong to the Karp's list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-Set Packing is (k+epsilon)/2 and goes back to the work of Hurkens and Schrijver [SIDMA'89], which gives (1.5+epsilon)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of this paper is a new approach to local search for k-Set Packing where only a special type of swaps is considered, which we call swaps of bounded path width. We show that for a fixed value of k one can search the space of r-size swaps of constant path width in cr poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant path width yields a polynomial time (k+1+epsilon)/3-approximation algorithm, improving the best known approximation ratio for k-Set Packing. In particular we improve the approximation ratio for 3-Dimensional Matching from 3/2+epsilon to 4/3+ε.