Stochastic graph exploration with limited resources

DOI10.1007/978-3-031-18367-6_9MaRDI QIDQ6176558zbMATH OpenOpenAlexFDO

Authors 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

graph explorationnon-adaptive strategiesstochastic optimization

Mathematics Subject Classification ID

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

Recommendations

• Stochastic graph exploration
• Learning unknown graphs
• Predicting the labels of an unknown graph via adaptive exploration
• Online Graph Exploration: New Results on Old and New Algorithms
• Online graph exploration with advice

Cites work

• A stochastic probing problem with applications
• Algorithms and adaptivity gaps for stochastic probing
• An adversarial model for scheduling with testing
• 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
• Collective dynamics of `small-world' networks
• Explorable uncertainty in scheduling with non-uniform testing times
• scientific article; zbMATH DE number 7650393 (Why is no real title available?)
• scientific article; zbMATH DE number 7740865 (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
• Scheduling with testing on multiple identical parallel machines
• Stochastic graph exploration
• The price of information in combinatorial optimization
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

Cited in

(5)

• Exploration of a finite graph by a collective of agents
• Undirected Graph Exploration with ⊝(log log n) Pebbles
• Optimal Node Visitation in Stochastic Digraphs
• Stochastic graph exploration
• scientific article; zbMATH DE number 7740865 (Why is no real title available?)

This page was built for publication: Stochastic graph exploration with limited resources

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