TSP with neighborhoods of varying size

de Berg, Mark (författare)

Gudmundsson, Joachim (författare)

Katz, Matthew (författare)

Levcopoulos, Christos (författare): Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science

Overmars, Mark (författare)

van der Stappen, Frank (författare)

(creator_code:org_t)

2002-08-29
2002
Engelska.
Ingår i: Algorithms — ESA 2002 / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 2461, s. 187-199

Relaterad länk:: http://dx.doi.org/10...; visa fler...; http://www.cs.uu.nl/...; https://lup.lub.lu.s...; https://doi.org/10.1...; visa färre...

Abstract Ämnesord

Stäng

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.

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.