On the adaptivity gap of stochastic orienteering

DOI10.1007/S10107-015-0927-9MaRDI QIDQ896283zbMATH OpenOpenAlexFDO

Authors N. Bansal, Viswanath Nagarajan

Publication date 9 December 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.3623

zbMATH Keywords

approximation algorithmsstochasticvehicle routing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06) Stochastic network models in operations research (90B15) Stochastic scheduling theory in operations research (90B36)

Abstract: The input to the stochastic orienteering problem consists of a budget $B$ and metric $(V,d)$ where each vertex $v$ has a job with deterministic reward and random processing time (drawn from a known distribution). The processing times are independent across vertices. The goal is to obtain a non-anticipatory policy 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 is one that 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 expected rewards of the optimal adaptive and non-adaptive policies. We prove an $Omega(loglogB{)}^{1/2}$ lower bound on the adaptivity gap of stochastic orienteering. This provides a negative answer to the $O(1)$ adaptivity gap conjectured earlier, and comes close to the $O(loglogB)$ upper bound. This result holds even on a line metric. We also show an $O(loglogB)$ 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 approximation algorithm for correlated stochastic orienteering.

Recommendations

• On the adaptivity gap of stochastic orienteering
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• scientific article; zbMATH DE number 7053373
• Constant approximation for stochastic orienteering problem with \((1+\epsilon)\)-budget relaxation
• Approximating the stochastic Knapsack problem: the benefit of adaptivity

Cites work

• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• Approximating Matches Made in Heaven
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Improved algorithms for orienteering and related problems
• Improved approximation results for stochastic knapsack problems
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• Learning Theory
• Multi-armed Bandits with Metric Switching Costs
• On the adaptivity gap of stochastic orienteering
• The orienteering problem
• The orienteering problem: a survey
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

Cited in

(5)

• Approximation algorithms for stochastic \(k\)-TSP
• On the adaptivity gap of stochastic orienteering
• An adversarial model for scheduling with testing
• Constant approximation for stochastic orienteering problem with \((1+\epsilon)\)-budget relaxation
• Non-adaptive stochastic score classification and explainable halfspace evaluation

This page was built for publication: On the adaptivity gap of stochastic orienteering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896283)