up 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.

 Postscript    Pdf    BibTeX  
 


Elias Koutsoupias / elias_at_di.uoa.gr