The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911260366340096 |
|---|---|
| author | Villa, Tullio Vercesi, Eleonora Barta, Janos Mastrolilli, Monaldo |
| author_facet | Villa, Tullio Vercesi, Eleonora Barta, Janos Mastrolilli, Monaldo |
| contents | We address the classical Dantzig - Fulkerson - Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution has at most n + 6 non-zero components, then the conjecture is true. To establish this result, we devise a new methodology that combines theoretical analysis and computational verification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07003 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components Villa, Tullio Vercesi, Eleonora Barta, Janos Mastrolilli, Monaldo Discrete Mathematics Optimization and Control We address the classical Dantzig - Fulkerson - Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution has at most n + 6 non-zero components, then the conjecture is true. To establish this result, we devise a new methodology that combines theoretical analysis and computational verification. |
| title | The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2507.07003 |