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},
}