Extending Exact Integrality Gap Computations for the Metric TSP

Abstract

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 to a larger number 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 $n=16$ vertices in the general case. Restricted to half-integral extreme points, we extend the enumeration to $n=18$. 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).

We extended the enumeration to n=16 in the general case and to n=18 in the half-integral case