Schalekamp–Williamson–van Zuylen conjecture on the subtour-LP integrality gap
Consider the metric traveling salesperson problem and its subtour linear programming relaxation. A feasible solution is half-integral if every edge variable satisfies . 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 -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
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.