The euclidean orienteering problem revisited

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 n^O(1/ε) time; the computed path visits at least (1 - ε{lunate})k_opt points of P, where k_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.