TSP with neighborhoods of varying size

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.

Gudmundsson, Joachim (författare)
Katz, Matthew (författare)
Levcopoulos, ChristosLund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science(Swepub:lu)cs-cle (författare)
Overmars, Mark (författare)
van der Stappen, Frank (författare)
Data VetenskapNaturvetenskapliga fakulteten (creator_code:org_t)

Ingår i:Algorithms — ESA 2002 / Lecture notes in computer scienceBerlin, Heidelberg : Springer Berlin Heidelberg2461, s. 187-1991611-33490302-9743

Av författaren/redakt...: de Berg, Mark; Gudmundsson, Joa ...; Katz, Matthew; Levcopoulos, Chr ...; Overmars, Mark; van der Stappen, ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.