M. Grigni, E. Koutsoupias, and C. Papadimitriou.

**An approximation scheme for planar graph TSP.**In*Proceedings of the 36th Annual Symposium on Foundations of Computer Science*, pages 640--645, Milwaukee, Wisconsin, 23--25 October 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 present a polynomial-time approximation scheme (PTAS) for this problem.### Bib

@string{FOCS95 = {Proceedings of the 36th Annual Symposium on Foundations of Computer Science}} @InProceedings{GKP95, author = {M. Grigni and E. Koutsoupias and C. Papadimitriou}, title = {An approximation scheme for planar graph {TSP}}, booktitle = FOCS95, year = 1995, month = {23--25 } # oct, pages = {640--645}, address = {Milwaukee, Wisconsin}, }