Journal
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
Volume 19, Issue 2, Pages 173-193Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0218195909002897
Keywords
Approximation algorithms; Euclidean TSP; group Steiner tree; connected neighborhoods; fat objects; packing lemmas
Ask authors/readers for more resources
In the Euclidean traveling salesman problem with discrete neighborhoods, we are given a set of points P in the plane and a set of n connected regions (neighborhoods), each containing at least one point of P. We seek to find a tour of minimum length which visits at least one point in each region. We give (i) an O(alpha)-approximation algorithm for the case when the regions are disjoint and alpha-fat, with possibly varying size; (ii) an O(alpha(3))-approximation algorithm for intersecting alpha-fat regions with comparable diameters. These results also apply to the case with continuous neighborhoods, where the sought TSP tour can hit each region at any point. We also give (iii) a simple O(log n)- approximation algorithm for continuous non-fat neighborhoods. The most distinguishing features of these algorithms are their simplicity and low running-time complexities.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available