Guest column: the elusive inapproximability of the TSP

摘要: After two decades of progress in hardness approximation we finally completely understand the extent to which many optimization problems can be approximated polynomial time. Unfortunately, however, and despite significant efforts, important continue resist such an understanding. One example is famous Traveling Salesman Problem, for best currently known bounds are strongly believed quite far from truth. In this article, describe main tools techniques used lower problem. Among them expander-like graph constructions called amplifiers bounded-occurrence instances standard constraint satisfaction problems. We also discuss how these ideas could (modestly) improved, (and whether) they may prove useful eventually resolving problem what ingredients still missing.