# 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