Although the Traveling Salesman Problem is one of the most intensely studied problems in combinatorics, the best currently known hardness of approximation bounds are a long way off the guarantee provided by the best approximation algorithms. In this talk we will discuss two recent hardness proofs which slightly improve the inapproximability bounds for both TSP and ATSP, after more than a decade. Though the gap between upper and lower bounds remains huge, our approach will emphasize simplicity and modularity, leaving some reasonable hope that further improvements are still possible. The main ingredients used will be Constraint Satisfaction Problems where each variable appears a bounded number of times, some special classes of expander-like graphs called amplifiers, and a healthy dose of gadgeteering.
The results presented are based on work which appeared in APPROX'12 as well as recent joint work with Marek Karpinski and Richard Schmied.