An Improved Approximation Algorithm for TSP in the Half Integral Case

DOI10.1145/3357713.3384273arXiv1908.00227MaRDI QIDQ6323008FDOQ6323008

Authors: Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan 

Publication date: 1 August 2019

Abstract: We design a $1.49993$-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention over the last decade due to a conjecture of Schalekamp, Williamson and van Zuylen stating that half-integral LP solutions have the largest integrality gap over all fractional solutions. So, if the conjecture of Schalekamp et al. holds true, our result shows that the integrality gap of the subtour polytope is bounded away from $3/2$.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: An Improved Approximation Algorithm for TSP in the Half Integral Case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323008)