Paper Info
Title
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem.
Abstract
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 to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma [The Symmetric Circulant Traveling Salesman Problem, Research Memorandum 429, Institute of Economic Research, University of Groningen, 1991]. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few nontrivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas [Math. Programming, 60 (1993), pp. 145-166] in a distinctly nonmetric set of instances.
Year
DOI
Venue
2019
10.1137/19M1245840
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
traveling salesman problem,linear program relaxation,integrality gap,subtour LP,approximation algorithms,circulant
Discrete mathematics,Approximation algorithm,Combinatorics,Circulant matrix,Travelling salesman problem,Linear programming,Mathematics
Journal
Volume
Issue
ISSN
33
4
0895-4801
Citations 
PageRank 
References 
0
0.34
14
Authors
2
Name
Order
Citations
PageRank
Samuel C. Gutekunst100.34
David P. Williamson23564413.34