Document Open Access Logo

Stochastic Graph Exploration

Authors Aris Anagnostopoulos, Ilan R. Cohen, Stefano Leonardi, Jakub Łącki

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.136.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Aris Anagnostopoulos
  • Sapienza University of Rome, Italy
Ilan R. Cohen
  • CWI, Amsterdam, The Netherlands
Stefano Leonardi
  • Sapienza University of Rome, Italy
Jakub Łącki
  • Google Research, New York, USA

Funding

  • Leonardi, Stefano: Partially supported by ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism Design Research in Online Markets".

Acknowledgements

The authors would like to thank Yossi Azar, Anupam Gupta, Peter Auer and C. Seshadhri for fruitful discussions.

Cite AsGet BibTex

Aris Anagnostopoulos, Ilan R. Cohen, Stefano Leonardi, and Jakub Łącki. Stochastic Graph Exploration. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 136:1-136:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.136

Abstract

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process. To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G=(V,E) with a source vertex s, stochastic edge costs drawn from a distribution pi_e, e in E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied. Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Omega(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(log nR) resource augmentation suffices to obtain O(1) approximation on trees and O(log nR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process - the minesweeper problem - which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(log nR) approximation for general graphs. We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1+epsilon budget, whose adaptivity gaps on trees and general graphs are 1+epsilon and 8+epsilon, respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Stochastic approximation
Keywords
  • stochastic optimization
  • graph exploration
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Marek Adamczyk. Improved analysis of the greedy algorithm for stochastic matching. Information Processing Letters, 111(15):731-737, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.05.007.
  2. Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica, 63(4):733-762, August 2012. Google Scholar
  3. Nikhil Bansal and Viswanath Nagarajan. On the Adaptivity Gap of Stochastic Orienteering, pages 114-125. Springer International Publishing, Cham, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07557-0_10.
  4. Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved Approximation Results for Stochastic Knapsack Problems, pages 1647-1665. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.127.
  5. Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria Minkoff. Approximation Algorithms for Orienteering and Discounted-Reward TSP. SIAM Journal on Computing, 37(2):653-670, 2007. Google Scholar
  6. Michael Caldera, Pisanu Buphamalai, Felix Mueller, and Jorg Menche. Interactome-based approaches to human disease. Current Opinion in Systems Biology, 3:88-94, 2017. Google Scholar
  7. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating Matches Made in Heaven, pages 266-278. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02927-1_23.
  8. Brian C. Dean, Michel X. Goemans, and Jan Vondrak. Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. Mathematics of Operations Research, 33(4):945-964, 2008. URL: http://dx.doi.org/10.1287/moor.1080.0330.
  9. Esther Frostig and Gideon Weiss. Four proofs of gittins multiarmed bandit theorem, 1999. Google Scholar
  10. Author(s) J. C. Gittins and J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, pages 148-177, 1979. Google Scholar
  11. Sudipto Guha and Kamesh Munagala. Approximation Algorithms for Budgeted Learning Problems. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 104-113, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1250790.1250807.
  12. Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 827-836, 2011. Google Scholar
  13. Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, and R. Ravi. Running Errands in Time: Approximation Algorithms for Stochastic Orienteering. Mathematics of Operations Research, 40(1):56-79, 2015. Google Scholar
  14. Anupam Gupta and Viswanath Nagarajan. A Stochastic Probing Problem with Applications, pages 205-216. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. Google Scholar
  15. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic Probing. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1731-1747, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884555.
  16. R. Laishram, K. Areekijseree, and S. Soundarajan. Predicted max degree sampling: Sampling in directed networks to maximize node coverage through crawling. In 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 940-945, May 2017. URL: http://dx.doi.org/10.1109/INFCOMW.2017.8116502.
  17. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
  18. Jure Leskovec and Rok Sosič. SNAP: A General-Purpose Network Analysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016. Google Scholar
  19. Will Ma. Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract, pages 1154-1163. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.85.
  20. S. Soundarajan, T. Eliassi-Rad, B. Gallagher, and A. Pinar. MaxReach: Reducing network incompleteness through node probes. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 152-157, August 2016. URL: http://dx.doi.org/10.1109/ASONAM.2016.7752227.
  21. Sucheta Soundarajan, Tina Eliassi-Rad, Brian Gallagher, and Ali Pinar. epsilon W GXX: Adaptive Edge Probing for Enhancing Incomplete Networks. In Proceedings of the 2017 ACM on Web Science Conference, WebSci '17, pages 161-170, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3091478.3091492.
  22. M. Vidal, ME Cusick, and AL Barabasi. Interactome networks and human disease. Cell., 144(6):986-98, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact