Advanced

TSP with neighborhoods of varying size

de Berg, M; Gudmundsson, J; Katz, MJ; Levcopoulos, Christos LU ; Overmars, MH and van der Stappen, AF (2005) In Journal of Algorithms 57(1). p.22-36
Abstract
In TSP with neighborhoods (TSPN) we are given a collection S of regions 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 neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN 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
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
approximation algorithms, TSP with neighborhoods, computational geometry
in
Journal of Algorithms
volume
57
issue
1
pages
22 - 36
publisher
Elsevier
external identifiers
  • wos:000232283200002
  • scopus:24944449883
ISSN
1090-2678
DOI
10.1016/j.jalgor.2005.01.010
project
VR 2002-4049
language
English
LU publication?
yes
id
cbf6256e-ca25-4a76-8736-0f7e6fbde4be (old id 221400)
date added to LUP
2007-09-21 11:23:43
date last changed
2017-08-13 03:38:57
@article{cbf6256e-ca25-4a76-8736-0f7e6fbde4be,
  abstract     = {In TSP with neighborhoods (TSPN) we are given a collection S of regions 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 neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P = NP.},
  author       = {de Berg, M and Gudmundsson, J and Katz, MJ and Levcopoulos, Christos and Overmars, MH and van der Stappen, AF},
  issn         = {1090-2678},
  keyword      = {approximation algorithms,TSP with neighborhoods,computational geometry},
  language     = {eng},
  number       = {1},
  pages        = {22--36},
  publisher    = {Elsevier},
  series       = {Journal of Algorithms},
  title        = {TSP with neighborhoods of varying size},
  url          = {http://dx.doi.org/10.1016/j.jalgor.2005.01.010},
  volume       = {57},
  year         = {2005},
}