摘要：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}$.
