Improved algorithms for orienteering and related problems
Authors:
Open Access
- 24 July 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 8 (3) , 1-27
Abstract
In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph G =( V, E ) (directed or undirected), two nodes s, t ∈ V and a time limit B , find an s - t walk in G of total length at most B that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as k -MST. Orienteering with time-windows is the more general problem in which each node v has a specified time-window [ R ( v ), D ( v )] and a node v is counted as visited by the walk only if v is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following: — A (2+ϵ) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004]. — An O (log 2 OPT) approximation for orienteering in directed graphs, where OPT ≤ n is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and Pál [2005] achieved a polylogarithmic approximation (a ratio of O (log OPT)). — Given an α approximation for orienteering, we show an O (α ċ max{log OPT, log l max / l min }) approximation for orienteering with time-windows, where l max and l min are the lengths of the longest and shortest time-windows respectively.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF 0728782)
This publication has 17 references indexed in Scilit:
- The Euclidean Orienteering Problem RevisitedSIAM Journal on Computing, 2008
- Approximation Algorithms for Orienteering and Discounted-Reward TSPSIAM Journal on Computing, 2007
- A 2 + ɛ approximation algorithm for the k-MST problemMathematical Programming, 2005
- On approximating a geometric prize-collecting traveling salesman problem with time windowsJournal of Algorithms, 2005
- A Constant-Factor Approximation Algorithm for thek-MST ProblemJournal of Computer and System Sciences, 1999
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting SalesmenSIAM Journal on Computing, 1998
- A General Approximation Technique for Constrained Forest ProblemsSIAM Journal on Computing, 1995
- Special cases of traveling salesman and repairman problems with time windowsNetworks, 1992
- The prize collecting traveling salesman problemNetworks, 1989
- On the worst‐case performance of some algorithms for the asymmetric traveling salesman problemNetworks, 1982