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 r poly(|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+ε.

Authors

• Marek Cygan

Keywords

• Bismuth
• Approximation methods
• Algorithm design and analysis
• Color
• Polynomials
• Approximation algorithms
• Standards
• Local Search
• Path Width
• 3-dimensional Matching
• Cardinality
• Local Maxima
• Estimation Algorithm
• Local Search Algorithm
• Packing Problem
• Upper Bound
• Hardness
• Undirected
• Average Degree
• Vertices
• Complex Parameters
• Combinatorial Optimization Problem
• Part Of The Proof
• Common Endpoint
• Logarithm Of Size
• Subset Of Vertices
• Linear Programming Relaxation
• approximation
• k-set packing
• fixed parameter tractability