A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP
Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Wołoszyn · 1997
Given a planar graph on n nodes with costs (weights) on its edges, de ne the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric TSP. For any ">0, our algorithm nds a salesman tour of total cost at most (1 + ") times optimal in time n O(1="2). We also present a quasi-polynomial time algorithm for the Steiner version of this problem.