arXiv preprint ·
Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a deterministic polynomial-time $1.6908$-approximation for Maximum Weighted $3$-Set Packing, breaking the $\sqrt3$ locality-gap barrier of squared-weight local search. The approximation ratio for this problem progressed from Berman's $2$ [Ber00] to Neuwohner's $2-\frac{1}{63{,}700{,}992}+ε$ [Neu21]. Thiery and Ward then obtained $1.786$ [TW23], while Thiery subsequently improved the bound to $1.761+ε$ and finally to $\sqrt3 \approx 1.732051$ through a layered exchange analysis [Thi23]. Thiery also proved that $\sqrt3$ is a locality-gap lower bound for the squared-weight objective even with exchanges of arbitrary size. Our algorithm performs in two phases and combines two objectives. Phase~I computes a bounded-exchange local optimum for the squared-weight potential and analyzes it through Thiery's layered framework, while strengthening the terminal analysis by preserving internal tree-edge slack for nonsingleton components and exploiting the incidence structure of $3$-sets for final singletons. This yields an augmented structural inequality with residual positive claw gain under the original objective. Phase~II switches to the original objective and recovers sufficient residual gain through an auxiliary weighted $9$-Set Packing instance. A covering argument transfers the structural bound through the high-girth lift used only in the analysis.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Envy-free Allocations with Individual Payments
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.