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).