Volume 10 (2014)
Article 9 pp. 217-236
Improved Inapproximability for TSP
Received: November 28, 2012
Revised: November 27, 2013
Published: September 27, 2014
Revised: November 27, 2013
Published: September 27, 2014
Keywords: inapproximability, traveling salesman
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40
Abstract: [Plain Text Version]
The Traveling Salesman Problem is one of the most studied problems in the theory of algorithms and its approximability is a long-standing open question. Prior to the present work, the best known inapproximability threshold was $\frac{220}{219}$, due to Papadimitriou and Vempala. Here, using an essentially different construction and also relying on the work of Berman and Karpinski on bounded-occurrence CSPs, we give an alternative and simpler inapproximability proof which improves the bound to $\frac{185}{184}$.
A conference version of this paper appeared in the Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2012).
Licensed under a Creative Commons Attribution License (CC-BY)