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 pairwise disjoint sets. A special case of 3-SET PACKING is the well known 3-DIMENSIONAL MATCHING problem, which is a maximum hypermatching problem in 3-uniform tripartite hypergraphs. 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 + ε)/2 and goes back to the work of Hurkens and Schrijver [SIDMA´89], which gives (1.5+ε)-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 pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c^rpoly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k+1+ε)/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+ε to 4/3+ε.