The Euclidean Traveling Salesman Problem is NP-hard. In 1976,
Christofides discovered a polynomial-time algorithm that always
computes a salesman tour whose cost is at most 1.5 times the optimal.
No better algorithm has been discovered since.
In this talk we will present a new algorithm that is an approximation
scheme: for any fixed c>0, it computes a tour whose cost is at most
1+c times the optimal. The running time is n^{O(1/c)}.
The algorithm generalizes to many other geometric problems, including
the famous Minimum Steiner Tree problem. It also generalizes (with some
increase in running time) to d-dimensional instances.