Extending Exact Integrality Gap Computations for the Metric TSP

William Cook, Stefan Hougardy, Moritz Petrich

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 assert…