Stochastic graph exploration

DOI10.4230/LIPICS.ICALP.2019.136MaRDI QIDQ5092339zbMATH OpenOpenAlexFDO

Authors Aris Anagnostopoulos, Ilan Reuven Cohen, Jakub Łącki, 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

approximation algorithmsgraph explorationstochastic optimization

Mathematics Subject Classification ID

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

Recommendations

• Stochastic graph exploration with limited resources
• Algorithms and adaptivity gaps for stochastic probing
• scientific article; zbMATH DE number 7053373
• The price of information in combinatorial optimization
• On the adaptivity gap of stochastic orienteering

Cites work

• A stochastic probing problem with applications
• Algorithms and adaptivity gaps for stochastic probing
• Approximating Matches Made in Heaven
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation algorithms for budgeted learning problems
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• scientific article; zbMATH DE number 3638998 (Why is no real title available?)
• Improved analysis of the greedy algorithm for stochastic matching
• Improved approximation results for stochastic knapsack problems
• Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: extended abstract
• On the adaptivity gap of stochastic orienteering
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

Cited in

(9)

• Exploration of a finite graph by a collective of agents
• Exploring an unknown graph
• Exploring Unknown Undirected Graphs
• Optimal Node Visitation in Stochastic Digraphs
• Deterministic Graph Exploration with Advice
• scientific article; zbMATH DE number 5263405 (Why is no real title available?)
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 7740865 (Why is no real title available?)
• Stochastic graph exploration with limited resources

This page was built for publication: Stochastic graph exploration

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