Du är här

TSP with neighborhoods of varying size

Författare:
Publiceringsår: 2005
Språk: Engelska
Sidor: 22-36
Publikation/Tidskrift/Serie: Journal of algorithms
Volym: 57
Nummer: 1
Dokumenttyp: Artikel
Förlag: Elsevier

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • approximation algorithms
  • TSP with neighborhoods
  • computational geometry

Övriga

Published
  • VR 2002-4049
Yes
  • ISSN: 0196-6774

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

LERU logotype U21 logotype

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen