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

About 5 years old · traced to

Let an instance have a fixed number of vertices, and let x∗x^* 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.

References

Primary source

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

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.