De Klerk–Dobre conjecture on the subtour LP for circulant TSP
De Klerk–Dobre conjecture on the subtour LP for circulant TSP
Let be the edge costs of a circulant instance and let be an associated stripe permutation. Let denote the optimal value of the subtour LP, and let denote the combinatorial lower bound
De Klerk–Dobre conjecture. For every circulant TSP instance,
De Klerk and Dobre supported this equality with numerical experiments; the subtour LP is known to be at least as strong as the VDV bound, while equality in general remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Samuel C. Gutekunst and David P. Williamson, “Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem”, arXiv:1902.06808 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.