2019/02/18 by Samuel C. Gutekunst, David P. Williamson, Gutekunst, Samuel C. +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1902.06808
openalex publication_date 2019/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the integrality gap of the subtour LP relaxation of the Traveling\nSalesman Problem restricted to circulant instances. De Klerk and Dobre\nconjectured that the value of the optimal solution to the subtour LP on these\ninstances is equal to an entirely combinatorial lower bound from Van der Veen,\nVan Dal, and Sierksma. We prove this conjecture by giving an explicit optimal\nsolution to the subtour LP. We then use it to show that the integrality gap of\nthe subtour LP is 2 on circulant instances, making such instances one of the\nfew non-trivial classes of TSP instances for which the integrality gap of the\nsubtour LP is exactly known. We also show that the degree constraints do not\nstrengthen the subtour LP on circulant instances, mimicking the parsimonious\nproperty of metric, symmetric TSP instances shown in Goemans and Bertsimas in a\ndistinctly non-metric set of instances.\n