De Klerk–Dobre conjecture on the subtour LP for circulant TSP

From papers

Let c1,,cdc_1,\ldots,c_d be the edge costs of a circulant instance and let ϕ\phi be an associated stripe permutation. Let OPTLP\operatorname{OPT}_{\mathrm{LP}} denote the optimal value of the subtour LP, and let VDV\operatorname{VDV} denote the combinatorial lower bound

VDV=(i=1(gi1ϕgiϕ)cϕ(i))+cϕ().\operatorname{VDV}=\left(\sum_{i=1}^{\ell}(g_{i-1}^{\phi}-g_i^{\phi})c_{\phi(i)}\right)+c_{\phi(\ell)}.

De Klerk–Dobre conjecture. For every circulant TSP instance,

VDV=OPTLP.\operatorname{VDV}=\operatorname{OPT}_{\mathrm{LP}}.

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

No solutions have been posted yet.