The Euclidean Orienteering Problem Revisited

Abstract

We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point $r \in P$, and a length constraint B, 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-\varepsilon)$-approximation algorithm for this problem that runs in $n^{O(1/\varepsilon)}$ time; the computed path visits at least $ (1-\varepsilon)k_{\mathrm{opt}}$ points of P, where $k_{\mathrm{opt}}$ 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.