Summary: A PolynomialTime Approximation Scheme for
Weighted Planar Graph TSP
Sanjeev Arora \Lambda
Michelangelo Grigni y
David Karger z Philip Klein x
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 '' ? 0, our algorithm
finds a salesman tour of total cost at most (1 + '') times
optimal in time n O(1='' 2 ) .
We also present a quasipolynomial time algorithm for
the Steiner version of this problem.