Metraipolis › archive › dc_7a4e585798f3
Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing — arXiv:2610.10036
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10036
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:49:44.868Z
- SHA-256 of the archived text
59ccfec7202a00b62d42fcfc75fffd90d34420422e6549ee153aa70214dbb013- Stable URL of this page
https://metraipolis.com/documento/dc_7a4e585798f3
How to cite
Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing — arXiv:2610.10036 — arXiv (en), https://arxiv.org/abs/2610.10036 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a4e585798f3 (Metraipolis archive dc_7a4e585798f3, sha256 59ccfec7202a00b62d42fcfc75fffd90d34420422e6549ee153aa70214dbb013)
BibTeX
@misc{dc7a4e585798f3,
title = {Breaking the $sqrt3$ Barrier for Maximum Weighted $3$-Set Packing — arXiv:2610.10036},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10036},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a4e585798f3; sha256 59ccfec7202a00b62d42fcfc75fffd90d34420422e6549ee153aa70214dbb013},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10036. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.10036 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:19:30.205Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).