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 ε 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(υ)] 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 ² 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 al [2005] achieved a polylogarithmic approximation (a ratio of O(logOPT)). -Given an α approximation for orienteering, we show an O(α · max{logOPT, log (Mathematical Equation Presented) }) approximation for orienteering with time-windows, where L _max and L _min are the lengths of the longest and shortest timewindows respectively.