Improved approximation for maximum weighted 3-set packing problem
Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing
Data Structures and Algorithms
Summary
The paper addresses the problem of selecting groups of three items so that these groups don't overlap and their total weight is as large as possible. Previous algorithms could only get close to about 1.732 times the best solution. The authors developed a new method that improves this approximation ratio to about 1.6908. They achieve this by combining two phases: first optimizing a related squared-weight measure, then using this to inform the final selection. This approach breaks a previously believed boundary and provides a better solution efficiently.
What this means in practice
- •For logistics planners: Improve packing schedules where items grouped in threes must be assigned without overlap, achieving more efficient resource allocation.
- •For network schedulers: Optimize task assignments in networks involving triplets of dependent jobs to improve throughput with better approximation guarantees.
A theory result. No direct application yet.
Authors
Weitian Tong, Yao Xu
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.