Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

TSP with neighborhoods of varying size

In English

Författare

  • 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.

Avdelning/ar

  • Computer Science

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

Ämne

  • 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/Övrigt

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