2013/10/01 by Marek Cygan · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Packing problems #Approximation algorithm #Local search (optimization) #Matching (statistics) #Discrete mathematics #Bounded function #Constant (computer programming) #Time complexity #Disjoint sets #Algorithm #Computer science #Statistics
paper · doi:10.1109/focs.2013.61
openalex publication_date 2013/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 crpoly(|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+ε.