The two-disjoint-triangles conjecture for maximum subtour-LP integrality ratio instances
Let an instance have a fixed number of vertices, and let 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: for all edges of two disjoint triangles, and or for all other edges . 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
- Xianghui Zhong, “Lower Bounds on the Integraliy Ratio of the Subtour LP for the Traveling Salesman Problem”, arXiv:2102.04765 (2021).
Progress summary
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.