On the adaptivity gap of stochastic orienteering

N. Bansal, V. Nagarajan

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

The input to the stochastic orienteering problem (Gupta et al. in SODA, pp 1522–1538,  2012) consists of a budget B and metric (V, d) where each vertex(Formula presented.) has a job with a deterministic reward and a random processing time (drawn from a known distribution). The processing times are independent across vertices. The goal is to obtain a non-anticipatory policy (originating from a given root vertex) to run jobs at different vertices, that maximizes expected reward, subject to the total distance traveled plus processing times being at most B. An adaptive policy can choose the next vertex to visit based on observed random instantiations. Whereas, a non-adaptive policy is just given by a fixed ordering of vertices. The adaptivity gap is the worst-case ratio of the optimal adaptive and non-adaptive rewards. We prove an (Formula presented.) lower bound on the adaptivity gap of stochastic orienteering. This provides a negative answer to the O(1)-adaptivity gap conjectured by Gupta et al. (2012), and comes close to the (Formula presented.) upper bound. This result holds even on a line metric. We also show an (Formula presented.) upper bound on the adaptivity gap for the correlated stochastic orienteering problem, where the reward of each job is random and possibly correlated to its processing time. Using this, we obtain an improved quasi-polynomial time (Formula presented.)-approximation algorithm for correlated stochastic orienteering.

Original languageEnglish
Pages (from-to)145-172
Number of pages28
JournalMathematical Programming
Volume154
Issue number1-2
DOIs
Publication statusPublished - 31 Dec 2015

Keywords

  • Approximation algorithms
  • Stochastic
  • Vehicle routing

Fingerprint

Dive into the research topics of 'On the adaptivity gap of stochastic orienteering'. Together they form a unique fingerprint.

Cite this