TRAVELING SALESMAN PROBLEM OF SEGMENTS
Jinhui Xu, Zhiyong Lin, Yang Yang, Ronald Berezney · International Journal of Computational Geometry & Applications · 2004
In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n ∊-separated segments in two dimensional space. Our results are based on an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique5 for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n2( log n)O(1/∊2)) time to compute a (1+∊)-approximation with probability ≥l/2, and can be derandomized with an additional factor of O(n2).