Improved algorithms for orienteering and related problems

Chandra Chekuri, Nitish Korula, Martin Pal

Research output: Contribution to journalArticlepeer-review


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 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 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.

Original languageEnglish (US)
Article number23
JournalACM Transactions on Algorithms
Issue number3
StatePublished - Jul 2012


  • Approximation algorithms
  • K-stroll
  • Orienteering
  • Orienteering with timewindows

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Improved algorithms for orienteering and related problems'. Together they form a unique fingerprint.

Cite this