DIMACS Theory Seminar


Title:

An Approximation Scheme for Planar Graph TSP

Speaker:

Michelangelo Grigni
Emory University

Place:

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

Time:

12:10 PM (Lunch will be served at 11:45 AM)
Friday, November 17, 1995

Abstract:

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)


dimacs-www@dimacs.rutgers.edu
Document last modified on November 14, 1995