The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

TSP with neighborhoods of varying size

På svenska

Author

  • Mark de Berg
  • Joachim Gudmundsson
  • Matthew Katz
  • Christos Levcopoulos
  • Mark Overmars
  • Frank van der Stappen

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

187-199

Publication/Series

Algorithms — ESA 2002 / Lecture notes in computer science

Volume

2461

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

10th Annual European Symposium on Algorithms, ESA 2002

Conference date

2002-09-17 - 2002-09-21

Conference place

Rome, Italy

Status

Published

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349