The orienteering problem in the plane revisited

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the orienteering problem: Given a set P of n points in the plane, a starting point r ε P, and a length constraint B, one needs to and a tour starting at r that visits as many points of P as possible and of length not exceeding B. We present a (1 -ε)-approximation algorithm for this problem that runs in no(I/ε) time, and visits at least (1 - ε)k opt points of P, where kopt is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
PublisherAssociation for Computing Machinery (ACM)
Pages247-253
Number of pages7
ISBN (Print)1595933409, 9781595933409
DOIs
StatePublished - 2006
Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
Duration: Jun 5 2006Jun 7 2006

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
Volume2006

Other

Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
CountryUnited States
CitySedona, AZ
Period6/5/066/7/06

Keywords

  • Approximation
  • Orienteering problem
  • k-TSP

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The orienteering problem in the plane revisited'. Together they form a unique fingerprint.

Cite this