View article

Given a planar graph on n nodes with costs (weights) on its edges, define 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 e> 0, our algorithm finds a salesman tour of total cost at most (1+ e) times optimal in time no (1/2) We also present a quasi-polynomial time algorithm for the Steiner version of this problem.