The two-disjoint-triangles conjecture for maximum subtour-LP integrality ratio instances
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.
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
Sign in to submit a solution.
No solutions have been posted yet.