TY - JOUR
T1 - Approximation algorithms for Euclidean group TSP and TSP with neighborhoods
AU - Elbassioni, K.M.
AU - Fishkin, A.V.
AU - Sitters, R.A.
PY - 2009
Y1 - 2009
N2 - 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(α)-approximation algorithm for the case when the regions are disjoint and α-fat, with possibly varying size; (ii) an O(α
AB - 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(α)-approximation algorithm for the case when the regions are disjoint and α-fat, with possibly varying size; (ii) an O(α
UR - https://www.scopus.com/pages/publications/66449105239
UR - https://www.scopus.com/inward/citedby.url?scp=66449105239&partnerID=8YFLogxK
U2 - 10.1142/S0218195909002897
DO - 10.1142/S0218195909002897
M3 - Article
SN - 0218-1959
VL - 19
SP - 173
EP - 193
JO - International Journal of Computational Geometry and Applications
JF - International Journal of Computational Geometry and Applications
ER -