In the Euclidean Traveling Salesman Problem (TSP), we are given $n$
points and are asked to determine the shortest path that visits all of
the points. Last year Sanjeev Arora astounded the algorithms community
by announcing a polynomial-time approximation algorithm for Euclidean
TSP. This problem has been long known to be NP-complete, and for nearly
20 years the best approximation known (due to Christofides) achieved an
approximation factor of 1.5.
Arora's most recent result is that, for any $c > 1$, it is possible
to construct a tour that is within a factor of $(1+1/c)$ of optimal
in time that is $O(n)$ times a polylogarithmic factor that depends on
$c$ and the dimension of the space. In the plane the running time is
$O(n (\log n)^{O(c)})$. This dramatic discovery combines two relatively
simple devices: quadtrees and dynamic programming.
In this talk I will present an informal and intuitive explanation of
Arora's algorithm. I hope that the talk will be accessible to anyone
with a basic knowledge of quadtrees and dynamic programming.