{"ID":2841673,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.11215","arxiv_id":"2511.11215","title":"TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima","abstract":"Determining the integrality gap of the linear programming (LP) relaxation of the metric traveling salesman problem (TSP) remains a long-standing open problem. We introduce a transfer principle: when the integer optimum of the 2-edge-connected multisubgraph problem (2ECM) is a unique Hamiltonian cycle $T$, any $α$-approximation algorithm for 2ECM that outputs a Hamiltonian cycle yields an $α$-approximation for TSP. We further develop a cut-margin stability framework that certifies $T$ as the unique integer optimum for both problems and is stable under $\\ell_\\infty$-bounded perturbations. We show that, if instances exist where the 2ECM has both a unique Hamiltonian cycle integer optimum and a half-integral LP solution, then the TSP integrality gap is at most 4/3 by the algorithm of Boyd et al. (SIAM Journal on Discrete Mathematics 36:1730--1747, 2022). Constructing such instances remains an open problem.","short_abstract":"Determining the integrality gap of the linear programming (LP) relaxation of the metric traveling salesman problem (TSP) remains a long-standing open problem. We introduce a transfer principle: when the integer optimum of the 2-edge-connected multisubgraph problem (2ECM) is a unique Hamiltonian cycle $T$, any $α$-appro...","url_abs":"https://arxiv.org/abs/2511.11215","url_pdf":"https://arxiv.org/pdf/2511.11215v2","authors":"[\"Toshiaki Yamanaka\"]","published":"2025-11-14T12:12:42Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\"]","methods":"[]","has_code":false}