DIMACS Theory Seminar
An Approximation Scheme for Planar Graph TSP
- Michelangelo Grigni
- Emory University
- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.
- 12:10 PM (Lunch will be served at 11:45 AM)
- Friday, November 17, 1995
We consider the special case of the traveling salesman problem (TSP)
in which the distance metric is the shortest-path metric of a planar
unweighted graph. We sketch a polynomial-time approximation scheme
(PTAS) for this problem, and propose some open problems for extending
the result to more general metrics.
(joint work with Elias Koutsoupias and Christos Papadimitriou,
Document last modified on November 14, 1995