Schalekamp–Williamson–van Zuylen conjecture on the subtour-LP integrality gap

About 7 years old · traced to

Consider the metric traveling salesperson problem and its subtour linear programming relaxation. A feasible solution is half-integral if every edge variable satisfies xe∈{0,1/2,1}x_e\in\{0,1/2,1\}. The integrality gap is the supremum, over instances, of the ratio between the cost of an optimal tour and the cost of an optimal subtour-LP solution. Schalekamp–Williamson–van Zuylen conjecture. The integrality gap for the subtour LP is attained on half-integral vertices of the polytope. Equivalently, half-integral LP solutions have the largest integrality gap among all fractional solutions. This conjecture identifies half-integral instances as the hardest instances for metric TSP. The paper's 1.499931.49993-approximation algorithm for half-integral solutions would imply the same upper bound for the subtour-LP integrality gap if the conjecture holds.

References

Primary source

Anna Karlin, Nathan Klein and Shayan Oveis Gharan, “An Improved Approximation Algorithm for TSP in the Half Integral Case”, arXiv:1908.00227 (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.