# Improved approximation for 3-dimensional matching via bounded pathwidth local search

arXiv: https://arxiv.org/abs/1304.1424 · HTML: https://mlsanity.com/paper/1304.1424/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2013.

## Built on by (most cited first, 2 of 2)

- [Ranking with Slot Constraints](https://mlsanity.com/paper/2310.17870/) (2023)
- [Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates](https://mlsanity.com/paper/2609.17951/) (2026)

## Abstract (arXiv)

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. 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 + eps)/2 and goes back to the work of Hurkens and Schrijver [SIDMA`89], which gives (1.5 + eps)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of the 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 + eps)/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 + eps to 4/3 + eps.