Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing
TL;DR
A deterministic polynomial-time approximation for Maximum Weighted $3-Set Packing, breaking the $\sqrt3$ locality-gap barrier of squared-weight local search and proving that $\sqrt3$ is a locality-gap lower bound for the squared-weight objective even with exchanges of arbitrary size.
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}+\epsilon$ [Neu21]. Thiery and Ward then obtained $1.786$ [TW23], while Thiery subsequently improved the bound to $1.761+\epsilon$ 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.
