Schalekamp–Williamson–van Zuylen conjecture on the subtour-LP integrality gap
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.
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
Anna Karlin, Nathan Klein and Shayan Oveis Gharan, “An Improved Approximation Algorithm for TSP in the Half Integral Case”, arXiv:1908.00227 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.