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

Summary, in English

In TSP with neighborhoods (TSPN) we are given a collection S of regions 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 neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN 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

2005

Språk

Engelska

Sidor

22-36

Publikation/Tidskrift/Serie

Journal of Algorithms

Volym

57

Issue

1

Dokumenttyp

Artikel i tidskrift

Förlag

Elsevier

Ämne

  • Computer Science

Nyckelord

  • approximation algorithms
  • TSP with neighborhoods
  • computational geometry

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISSN: 1090-2678