Stochastic graph exploration with limited resources

DOI10.1007/978-3-031-18367-6_9OpenAlexW4312644182MaRDI QIDQ6176558

Ilan Reuven Cohen

Publication date: 25 July 2023

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-18367-6_9

zbMATH Keywords

stochastic optimizationgraph explorationnon-adaptive strategies

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Scheduling with testing on multiple identical parallel machines
• Improved analysis of the greedy algorithm for stochastic matching
• Explorable uncertainty in scheduling with non-uniform testing times
• An adversarial model for scheduling with testing
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Approximating Matches Made in Heaven
• Algorithms and Adaptivity Gaps for Stochastic Probing
• A Stochastic Probing Problem with Applications
• Stochastic graph exploration
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Collective dynamics of ‘small-world’ networks
• 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