Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
We consider the integrality gap of the subtour linear program (LP) relaxation of the traveling salesman problem (TSP) restricted to circulant instances. De Klerk and Dobre [Discrete Appl. Math., 159 (2011), pp. 1815--1826] conjectured that the value of the optimal solution to the subtour LP in these instances is equal …