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, FOCS'95)

Document last modified on November 14, 1995