Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems
Speaker:
Sanjeev Arora
Princeton University
Place:
Room 402, Computer Science Building
35 Olden Street
Princeton University.
Time:
12:05 PM (Lunch will be served at 11:45 AM)
Thursday, April 10, 1997
Contact:
Sanjeev Arora (arora@cs.princeton.edu)
Abstract:
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.