Stochastic graph exploration

DOI10.4230/LIPIcs.ICALP.2019.136OpenAlexW2965209284MaRDI QIDQ5092339

Jakub Łącki, Aris Anagnostopoulos, Ilan Reuven Cohen, Stefano Leonardi

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10712/pdf/LIPIcs-ICALP-2019-136.pdf

zbMATH Keywords

stochastic optimizationapproximation algorithmsgraph exploration

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

Stochastic graph exploration with limited resources

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Improved analysis of the greedy algorithm for stochastic matching
• 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
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• On the Adaptivity Gap of Stochastic Orienteering
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

This page was built for publication: Stochastic graph exploration