Metraipolis › archive › dc_71bbdb5c6c16
Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations — arXiv:2611.05511
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05511
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:29.385Z
- SHA-256 of the archived text
0e69d65f4f11fb08f13ce67962916858577421f48e62c00b2c189533b59cb243- Stable URL of this page
https://metraipolis.com/documento/dc_71bbdb5c6c16
How to cite
Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations — arXiv:2611.05511 — arXiv (en), https://arxiv.org/abs/2611.05511 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_71bbdb5c6c16 (Metraipolis archive dc_71bbdb5c6c16, sha256 0e69d65f4f11fb08f13ce67962916858577421f48e62c00b2c189533b59cb243)
BibTeX
@misc{dc71bbdb5c6c16,
title = {Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations — arXiv:2611.05511},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05511},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_71bbdb5c6c16; sha256 0e69d65f4f11fb08f13ce67962916858577421f48e62c00b2c189533b59cb243},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05511. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms. The currently best approximation ratio for the problem is 1.2787, obtained recently by the authors (2026). The best lower bound on the approximation ratio that can be achieved for the problem in polynomial time, under the Unique Games Conjecture (UGC), is 1.20016, obtained by Bérczi, Chandrasekaran, Király, and Madan (2020), building on and slightly improving a bound of $\frac65=1.2$, obtained by Angelidakis, Makarychev, and Manurangsi (2017) by introducing the important framework of non-opposite multiway cuts. We obtain a substantially improved lower bound of 1.22232 on the approximation ratio of the Multiway Cut problem. Manokaran, Naor, Raghavendra, and Schwartz (2008) showed that under UGC, the approximation ratio of Multiway Cut is equal to the integrality ratio of a simple LP relaxation, known as the CKR relaxation, introduced by Călinescu, Karloff, and Rabani (2000). Thus, stronger LP relaxations are not required for obtaining an optimal approximation algorithm for the problem. We show, however, that relying on the framework of Angelidakis, Makarychev, and Manurangsi (2017), stronger LP relaxations from the Sherali-Adams hierarchy for non-opposite multiway cuts can be used to obtain improved integrality ratios for the CKR relaxation, and hence improved lower bounds on the approximation ratio of the Multiway Cut problem. One of the novel features of our analysis is considering a continuous limit of discrete LPs defined on a simplex. Our proof of the new 1.22232 bound is completely analytic. We also present strong numerical evidence that suggests that our techniques can be used to improve the lower bound to at least 1.23003. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2611.05511 — 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-11-05T18:21:04.020Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).