Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

TSP with neighborhoods of varying size

  • Mark de Berg
  • Joachim Gudmundsson
  • Matthew Katz
  • Christos Levcopoulos
  • Mark Overmars
  • Frank van der Stappen
Publiceringsår: 2002
Språk: Engelska
Sidor: 187-199
Publikation/Tidskrift/Serie: Algorithms — ESA 2002 / Lecture notes in computer science
Volym: 2461
Dokumenttyp: Konferensbidrag
Förlag: Springer


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.


  • Computer Science


10th Annual European Symposium on Algorithms, ESA 2002
  • ISSN: 0302-9743
  • ISSN: 1611-3349

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

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