Improved Algorithms for Orienteering and Related Problems
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 is an element of 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 + epsilon) 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 Pal [2005] achieved a polylogarithmic approximation (a ratio of O(logOPT)). -Given an alpha approximation for orienteering, we show an O(alpha . max{logOPT, logL(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.
algorithms orienteering approximation algorithms orienteering with time-windows theory k-stroll