DIMACS Princeton Theory Seminar

Title:

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.

Document last modified on March 28, 1997