a constant-factor approximation algorithm for tsp with pairwise-disjoint connected neighborhoods in the plane
In the Euclidean TSP with neighborhoods (TSPN) problem we seek. 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.
approximation algorithm tsp