TSP with neighborhoods of varying size
(2002) 10th Annual European Symposium on Algorithms, ESA 2002 2461. p.187-199- Abstract
- In TSP with neighborhoods we are given a set of objects in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the objects are of approximately the same size. We present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of arbitrary size. We also show that the problem is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/632293
- author
- de Berg, Mark ; Gudmundsson, Joachim ; Katz, Matthew ; Levcopoulos, Christos LU ; Overmars, Mark and van der Stappen, Frank
- organization
- publishing date
- 2002
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Algorithms — ESA 2002 / Lecture notes in computer science
- volume
- 2461
- pages
- 187 - 199
- publisher
- Springer
- conference name
- 10th Annual European Symposium on Algorithms, ESA 2002
- conference location
- Rome, Italy
- conference dates
- 2002-09-17 - 2002-09-21
- external identifiers
-
- wos:000181470400016
- scopus:84938061920
- ISSN
- 0302-9743
- 1611-3349
- DOI
- 10.1007/3-540-45749-6_20
- language
- English
- LU publication?
- yes
- id
- 6f753d39-3959-4d5d-af40-71442b304574 (old id 632293)
- date added to LUP
- 2016-04-01 11:42:26
- date last changed
- 2024-01-07 17:25:24
@inproceedings{6f753d39-3959-4d5d-af40-71442b304574, abstract = {{In TSP with neighborhoods we are given a set of objects in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the objects are of approximately the same size. We present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of arbitrary size. We also show that the problem is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.}}, author = {{de Berg, Mark and Gudmundsson, Joachim and Katz, Matthew and Levcopoulos, Christos and Overmars, Mark and van der Stappen, Frank}}, booktitle = {{Algorithms — ESA 2002 / Lecture notes in computer science}}, issn = {{0302-9743}}, language = {{eng}}, pages = {{187--199}}, publisher = {{Springer}}, title = {{TSP with neighborhoods of varying size}}, url = {{http://dx.doi.org/10.1007/3-540-45749-6_20}}, doi = {{10.1007/3-540-45749-6_20}}, volume = {{2461}}, year = {{2002}}, }