The Euclidean Orienteering Problem Revisited
Authors:
- Ke ChenKCKe Chen
- Sariel Har-PeledSHSariel Har-Peled
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (1) , 385-397
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.
Keywords
This publication has 12 references indexed in Scilit:
- A Recursive Greedy Algorithm for Walks in Directed Graphs2005
- On approximating a geometric prize-collecting traveling salesman problem with time windowsJournal of Algorithms, 2005
- Approximation algorithms for deadline-TSP and vehicle routing with time-windows2004
- Approximation algorithms for orienteering and discounted-reward TSP2004
- Approximation schemes for NP-hard geometric optimization problems: a surveyMathematical Programming, 2003
- Approximation Schemes for Minimum Latency ProblemsSIAM Journal on Computing, 2003
- The Vehicle Routing Problem2002
- Geometric Shortest Paths and Network Optimization2000
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related ProblemsSIAM Journal on Computing, 1999
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998