A polynomial-time approximation scheme for weighted planar graph TSP
Given a planar Rraph on n nodes with costs (weights) on its edges,define ;he distance between nodes i &d 2 as’ the length of the shortest path between i and i. Consider this as &I instance of me& TSP. For any E > 6, our algorithm finds a salesman tour of total cost at most (1 + E) times optimal in time n”(llea). We also present a quasi-polynomial time algorithm for the Steiner version of this problem.