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

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

22-36

Publication/Series

Journal of Algorithms

Volume

57

Issue

1

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Keywords

  • approximation algorithms
  • TSP with neighborhoods
  • computational geometry

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 1090-2678