Extending Exact Integrality Gap Computations for the Metric TSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915969833631744 |
|---|---|
| author | Cook, William Hougardy, Stefan Petrich, Moritz |
| author_facet | Cook, William Hougardy, Stefan Petrich, Moritz |
| contents | The subtour relaxation of the traveling salesman problem (TSP) plays a central role in approximation algorithms and polyhedral studies of the TSP. A long-standing conjecture asserts that the integrality gap of the subtour relaxation for the metric TSP is exactly 4/3. In this paper, we extend the exact verification of this conjecture for small numbers of vertices.
Using the framework introduced by Benoit and Boyd in 2008, we confirm their results up to n=10. We further show that for n=11 and n=12, the published lists of extreme points of the subtour polytope are incomplete: one extreme point is missing for n=11 and twenty-two extreme points are missing for n=12. We extend the enumeration of the extreme points of the subtour polytope to instances with up to 14 vertices in the general case. Restricted to half-integral vertices, we extend the enumeration of extreme points up to n=17. Our results provide additional support for the 4/3-Conjecture.
Our lists of extreme points are available on the public bonndata repository (https://doi.org/10.60507/FK2/JK95PC). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_12995 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Extending Exact Integrality Gap Computations for the Metric TSP Cook, William Hougardy, Stefan Petrich, Moritz Combinatorics Data Structures and Algorithms 68W25, 68W40, 68Q25, 90C27 F.2.2; G.2.1; G.2.2 The subtour relaxation of the traveling salesman problem (TSP) plays a central role in approximation algorithms and polyhedral studies of the TSP. A long-standing conjecture asserts that the integrality gap of the subtour relaxation for the metric TSP is exactly 4/3. In this paper, we extend the exact verification of this conjecture for small numbers of vertices. Using the framework introduced by Benoit and Boyd in 2008, we confirm their results up to n=10. We further show that for n=11 and n=12, the published lists of extreme points of the subtour polytope are incomplete: one extreme point is missing for n=11 and twenty-two extreme points are missing for n=12. We extend the enumeration of the extreme points of the subtour polytope to instances with up to 14 vertices in the general case. Restricted to half-integral vertices, we extend the enumeration of extreme points up to n=17. Our results provide additional support for the 4/3-Conjecture. Our lists of extreme points are available on the public bonndata repository (https://doi.org/10.60507/FK2/JK95PC). |
| title | Extending Exact Integrality Gap Computations for the Metric TSP |
| topic | Combinatorics Data Structures and Algorithms 68W25, 68W40, 68Q25, 90C27 F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2603.12995 |