TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918233137741824 |
|---|---|
| author | Yamanaka, Toshiaki |
| author_facet | Yamanaka, Toshiaki |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11215 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima Yamanaka, Toshiaki Optimization and Control Data Structures and Algorithms 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. |
| title | TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.11215 |