Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

TSP with neighborhoods of varying size

de Berg, Mark ; Gudmundsson, Joachim ; Katz, Matthew ; Levcopoulos, Christos LU orcid ; Overmars, Mark and van der Stappen, Frank (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:
author
; ; ; ; and
organization
publishing date
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
1611-3349
0302-9743
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         = {{1611-3349}},
  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}},
}