Extending Exact Integrality Gap Computations for the Metric TSP
This work provides incremental support for a long-standing conjecture in combinatorial optimization, relevant to researchers in approximation algorithms and polyhedral theory.
The paper tackles the verification of the 4/3 integrality gap conjecture for the metric TSP by extending exact computations to more vertices, confirming results up to n=10 and identifying missing extreme points for n=11 and n=12, with enumerations extended up to n=14 for general cases and n=17 for half-integral vertices.
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.