DIMACS Princeton Theory Seminar


Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems


Sanjeev Arora
Princeton University


Room 402, Computer Science Building
35 Olden Street
Princeton University.


12:05 PM (Lunch will be served at 11:45 AM)
Thursday, April 10, 1997


Sanjeev Arora (arora@cs.princeton.edu)


The Euclidean Traveling Salesman Problem is NP-hard. In 1976, Christofides discovered a polynomial-time approximation algorithm that finds a salesman tour of cost at most 1.5 times the optimal.

Last year we presented a new algorithm that is an approximation scheme: for any fixed c>0, it computes a tour of cost at most 1+c times the optimal. The scheme's running time was n^{O(1/c)}.

This talk will describe an approximation scheme that is simpler and much more efficient. For any fixed c>0, it finds a (1+c)-approximate tour in n*polylog(n) time, which is nearly linear in n. The scheme also works in nearly linear time on instances in d dimensions (for fixed d).

Our algorithm generalizes to many other geometric problems, including the famous Minimum Steiner Tree problem, and the Euclidean Matching problem.

Document last modified on March 28, 1997