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 ∊ 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 - ϵ)-approximation algorithm for this problem that runs in n^O(1/ϵ) time; the computed path visits at least (1 - ϵ)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. [ABSTRACT FROM AUTHOR]