The euclidean orienteering problem revisited

Research output: Contribution to journalArticlepeer-review


We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point r ε{lunate} P, and a length constraint, one needs to find a path starting from r that visits as many points of P as possible and of length not exceeding B. We present a (1 - ε{lunate})- approximation algorithm for this problem that runs in nO(1/ε) time; the computed path visits at least (1 - ε{lunate})kopt points of P, where kopt is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions.

Original languageEnglish (US)
Pages (from-to)385-397
Number of pages13
JournalSIAM Journal on Computing
Issue number1
StatePublished - 2008


  • Approximation algorithms
  • Orienteering problem
  • PTAS
  • k-TSP

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this