On the adaptivity gap of stochastic orienteering

DOI10.1007/S10107-015-0927-9zbMATH Open1337.90019arXiv1311.3623OpenAlexW1850832643MaRDI QIDQ896283FDOQ896283

N. Bansal, Viswanath Nagarajan

Publication date: 9 December 2015

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

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.

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

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

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)

Cites Work

• Learning Theory
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• The orienteering problem
• The orienteering problem: a survey
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Approximating Matches Made in Heaven
• Multi-armed Bandits with Metric Switching Costs
• Title not available (Why is that?)
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• On the Adaptivity Gap of Stochastic Orienteering
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Title not available (Why is that?)
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Improved algorithms for orienteering and related problems

Cited In (3)

• Title not available (Why is that?)
• An adversarial model for scheduling with testing
• 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)