Approximation algorithms for Euclidean group TSP and TSP with neighborhoods

K.M. Elbassioni; A.V. Fishkin; R.A. Sitters

doi:10.1142/S0218195909002897

Approximation algorithms for Euclidean group TSP and TSP with neighborhoods

K.M. Elbassioni, A.V. Fishkin, R.A. Sitters

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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(α

Original language	English
Pages (from-to)	173-193
Journal	International Journal of Computational Geometry and Applications
Volume	19
DOIs	https://doi.org/10.1142/S0218195909002897
Publication status	Published - 2009

Access to Document

10.1142/S0218195909002897

Persistent URL (handle)

Copy link address

Cite this

@article{ff30d77044db4536b143dab5de48740b,

title = "Approximation algorithms for Euclidean group TSP and TSP with neighborhoods",

abstract = "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(α",

author = "K.M. Elbassioni and A.V. Fishkin and R.A. Sitters",

year = "2009",

doi = "10.1142/S0218195909002897",

language = "English",

volume = "19",

pages = "173--193",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte Ltd",

}

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(α

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 -

Approximation algorithms for Euclidean group TSP and TSP with neighborhoods

Abstract

Access to Document

Persistent URL (handle)

Fingerprint

Cite this