Volume 10 (2014) Article 9 pp. 217-236
Improved Inapproximability for TSP
Received: November 28, 2012
Revised: November 27, 2013
Published: September 27, 2014
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}$.