The two-disjoint-triangles conjecture for maximum subtour-LP integrality ratio instances

From papers

Let an instance have a fixed number of vertices, and let xx^* be an optimal fractional solution of its subtour LP. The two-disjoint-triangles conjecture. The instances maximizing the integrality ratio among all instances with a fixed number of vertices have the following structure: x(e)=12x^*(e)=\frac{1}{2} for all edges ee of two disjoint triangles, and x(e)=0x^*(e)=0 or x(e)=1x^*(e)=1 for all other edges ee. The conjecture proposes a common structural form for extremal instances, extending the structures observed computationally for small numbers of vertices; whether it holds for every fixed number of vertices is not established in the supplied text.

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

Xianghui Zhong, “Lower Bounds on the Integraliy Ratio of the Subtour LP for the Traveling Salesman Problem”, arXiv:2102.04765 (2021).

Solutions 0

No solutions have been posted yet.