TY - GEN
T1 - A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
AU - Mitchell, Joseph S.B.
PY - 2010
Y1 - 2010
N2 - In the Euclidean TSP with neighborhoods (TSPN) problem we seek a shortest tour that visits a given set of n neighborhoods. The Euclidean TSPN generalizes the standard TSP on points. We present the first constant-factor approximation algorithm for planar TSPN with pairwise-disjoint connected neighborhoods of any size or shape. Prior approximation bounds were O(log n), except in special cases.
AB - In the Euclidean TSP with neighborhoods (TSPN) problem we seek a shortest tour that visits a given set of n neighborhoods. The Euclidean TSPN generalizes the standard TSP on points. We present the first constant-factor approximation algorithm for planar TSPN with pairwise-disjoint connected neighborhoods of any size or shape. Prior approximation bounds were O(log n), except in special cases.
UR - https://www.scopus.com/pages/publications/77954919609
U2 - 10.1145/1810959.1810992
DO - 10.1145/1810959.1810992
M3 - Conference contribution
AN - SCOPUS:77954919609
SN - 9781450300162
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 183
EP - 191
BT - Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
T2 - 26th Annual Symposium on Computational Geometry, SoCG 2010
Y2 - 13 June 2010 through 16 June 2010
ER -