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)

Document last modified on November 14, 1995