Running Errands in Time: Approximation Algorithms for Stochastic Orienteering

DOI10.1287/moor.2014.0656zbMath1328.90067OpenAlexW1983803998MaRDI QIDQ5245015

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

Publication date: 1 April 2015

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2014.0656

zbMATH Keywords

stochastic optimizationapproximation algorithmsorienteering problemadaptivity gap

Mathematics Subject Classification ID

Stochastic programming (90C15) Stochastic network models in operations research (90B15) Approximation methods and heuristics in mathematical programming (90C59) Stochastic scheduling theory in operations research (90B36) Approximation algorithms (68W25)

Related Items (10)

Faster algorithms for orienteering and \(k\)-TSP ⋮ Non-adaptive stochastic score classification and explainable halfspace evaluation ⋮ Stochastic graph exploration with limited resources ⋮ An adversarial model for scheduling with testing ⋮ The capacitated orienteering problem ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms ⋮ Stochastic graph exploration ⋮ Unnamed Item ⋮ Rollout-based routing strategies with embedded prediction: a fish trawling application

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed orienteering problem
• The orienteering problem with stochastic travel and service times
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• On tail probabilities for martingales
• Approximating optimal binary decision trees
• Approximation in stochastic scheduling
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Improved algorithms for orienteering and related problems
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
• The Euclidean Orienteering Problem Revisited
• Approximating Matches Made in Heaven
• A Characterization of Waiting Time Performance Realizable by Single-Server Queues
• On Multidimensional Packing Problems
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Multi-armed Bandits with Metric Switching Costs
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• On the Adaptivity Gap of Stochastic Orienteering
• Learning Theory
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

This page was built for publication: Running Errands in Time: Approximation Algorithms for Stochastic Orienteering