An approximation scheme for planar graph TSP

Michelangelo Grigni, Costas Papadimitriou

2002 · 115 citations · 9 references

Concepts

Abstract

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.

References

9