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

About 7 years old · traced to

Let c1,…,cdc_1,\ldots,c_d be the edge costs of a circulant instance and let ϕ\phi be an associated stripe permutation. Let OPT⁡LP\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ℓ(gi−1ϕ−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⁡=OPT⁡LP.\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.

References

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.