Running errands in time: Approximation algorithms for stochastic orienteering

Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi

Research output: Contribution to journalArticlepeer-review


In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log log B)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n log B)-approximation algorithm; here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps".

Original languageEnglish (US)
Pages (from-to)56-79
Number of pages24
JournalMathematics of Operations Research
Issue number1
StatePublished - Feb 15 2015


  • Adaptivity gap
  • Approximation algorithms
  • Orienteering problem
  • Stochastic optimization

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Running errands in time: Approximation algorithms for stochastic orienteering'. Together they form a unique fingerprint.

Cite this