An approximation scheme for planar graph TSP
Michelangelo Grigni, Elias Koutsoupias, Costas Papadimitriou · 2002
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.