{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:20:52Z","timestamp":1742991652566,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031183669"},{"type":"electronic","value":"9783031183676"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-18367-6_9","type":"book-chapter","created":{"date-parts":[[2022,10,20]],"date-time":"2022-10-20T16:05:36Z","timestamp":1666281936000},"page":"172-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stochastic Graph Exploration with\u00a0Limited Resources"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7870-6319","authenticated-orcid":false,"given":"Ilan Reuven","family":"Cohen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"issue":"15","key":"9_CR1","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.ipl.2011.05.007","volume":"111","author":"M Adamczyk","year":"2011","unstructured":"Adamczyk, M.: Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett. 111(15), 731\u2013737 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-030-80879-2_9","volume-title":"Approximation and Online Algorithms","author":"S Albers","year":"2021","unstructured":"Albers, S., Eckl, A.: Explorable uncertainty in scheduling with non-uniform testing times. In: Kaklamanis, C., Levin, A. (eds.) WAOA 2020. LNCS, vol. 12806, pp. 127\u2013142. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_9"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-030-83508-8_3","volume-title":"Algorithms and Data Structures","author":"S Albers","year":"2021","unstructured":"Albers, S., Eckl, A.: Scheduling with testing on multiple identical parallel machines. In: Lubiw, A., Salavatipour, M. (eds.) WADS 2021. LNCS, vol. 12808, pp. 29\u201342. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-83508-8_3"},{"key":"9_CR4","unstructured":"Anagnostopoulos, A., Cohen, I.R., Leonardi, S., Lacki, J.: Stochastic graph exploration. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Aouad, A., Ji, J., Shaposhnik, Y.: Pandora\u2019s box problem with sequential inspections. SSRN 3726167 (2020)","DOI":"10.2139\/ssrn.3726167"},{"key":"9_CR6","unstructured":"Bampis, E., D\u00fcrr, C., Erlebach, T., Santos de Lima, M., Megow, N., Schl\u00f6ter, J.: Orienting (hyper)graphs under explorable stochastic uncertainty. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal, 6\u20138 September 2021 (Virtual Conference). LIPIcs, vol. 204 pp. 10:1\u201310:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s00453-011-9511-8","volume":"63","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. Algorithmica 63(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-319-07557-0_10","volume-title":"Integer Programming and Combinatorial Optimization","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Nagarajan, V.: On the adaptivity gap of stochastic orienteering. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 114\u2013125. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07557-0_10"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Beyhaghi, H., Kleinberg, R.: Pandora\u2019s problem with nonobligatory inspection. In: Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 131\u2013132 (2019)","DOI":"10.1145\/3328526.3329626"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1647\u20131665. SIAM (2011)","DOI":"10.1137\/1.9781611973082.127"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Boodaghians, S., Fusco, F., Lazos, P., Leonardi, S.: Pandora\u2019s box problem with order constraints. In: Proceedings of the 21st ACM Conference on Economics and Computation, pp. 439\u2013458 (2020)","DOI":"10.1145\/3391403.3399501"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Chawla, S., Gergatsouli, E., Teng, Y., Tzamos, C., Zhang, R.: Pandora\u2019s box with correlations: learning and approximation. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 1214\u20131225. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00116"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-642-02927-1_23","volume-title":"Automata, Languages and Programming","author":"N Chen","year":"2009","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 266\u2013278. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_23"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Chugg, B., Maehara, T.: Submodular stochastic probing with prices. In: 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 60\u201366. IEEE (2019)","DOI":"10.1109\/CoDIT.2019.8820312"},{"issue":"4","key":"9_CR15","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1287\/moor.1080.0330","volume":"33","author":"BC Dean","year":"2008","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33(4), 945\u2013964 (2008)","journal-title":"Math. Oper. Res."},{"issue":"12","key":"9_CR16","doi-asserted-by":"publisher","first-page":"3630","DOI":"10.1007\/s00453-020-00742-2","volume":"82","author":"C D\u00fcrr","year":"2020","unstructured":"D\u00fcrr, C., Erlebach, T., Megow, N., Mei\u00dfner, J.: An adversarial model for scheduling with testing. Algorithmica 82(12), 3630\u20133675 (2020)","journal-title":"Algorithmica"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for budgeted learning problems. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, San Diego, California, USA, pp. 104\u2013113. ACM, New York (2007)","DOI":"10.1145\/1250790.1250807"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: 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, 22\u201325 October 2011, pp. 827\u2013836 (2011)","DOI":"10.1109\/FOCS.2011.48"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1287\/moor.2014.0656","volume":"40","author":"A Gupta","year":"2015","unstructured":"Gupta, A., Krishnaswamy, R., Nagarajan, V., Ravi, R.: Running errands in time: approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1), 56\u201379 (2015)","journal-title":"Math. Oper. Res."},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-642-36694-9_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Gupta","year":"2013","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Goemans, M., Correa, J. (eds.) IPCO 2013. LNCS, vol. 7801, pp. 205\u2013216. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36694-9_18"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V., Singla, S.: Algorithms and adaptivity gaps for stochastic probing. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, Virginia, pp. 1731\u20131747. Society for Industrial and Applied Mathematics, Philadelphia (2016)","DOI":"10.1137\/1.9781611974331.ch120"},{"key":"9_CR22","unstructured":"Jiang, H., Li, J., Liu, D., Singla, S.: Algorithms and adaptivity gaps for stochastic $$k$$-TSP. arXiv preprint arXiv:1911.02506 (2019)"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Laishram, R., Areekijseree, K., Soundarajan, S.: Predicted max degree sampling: sampling in directed networks to maximize node coverage through crawling. In: 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 940\u2013945 (2017)","DOI":"10.1109\/INFCOMW.2017.8116502"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1154\u20131163. SIAM (2014)","DOI":"10.1137\/1.9781611973402.85"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Singla, S.: The price of information in combinatorial optimization. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2523\u20132532. SIAM (2018)","DOI":"10.1137\/1.9781611975031.161"},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Soundarajan, S., Eliassi-Rad, T., Gallagher, B., Pinar, A.: MaxReach: reducing network incompleteness through node probes. In: 2016 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 152\u2013157 (2016)","DOI":"10.1109\/ASONAM.2016.7752227"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Soundarajan, S., Eliassi-Rad, T., Gallagher, B., Pinar, A.: $$\\epsilon $$WGXX: adaptive edge probing for enhancing incomplete networks. In: Proceedings of the 2017 ACM on Web Science Conference, WebSci 2017, New York, NY, USA, pp. 161\u2013170. ACM, New York (2017)","DOI":"10.1145\/3091478.3091492"},{"issue":"2","key":"9_CR28","doi-asserted-by":"publisher","first-page":"4185","DOI":"10.1109\/LRA.2021.3068699","volume":"6","author":"TC Thayer","year":"2021","unstructured":"Thayer, T.C., Carpin, S.: An adaptive method for the stochastic orienteering problem. IEEE Robot. Autom. Lett. 6(2), 4185\u20134192 (2021)","journal-title":"IEEE Robot. Autom. Lett."},{"key":"9_CR29","unstructured":"Wang, W., Gupta, A., Williams, J.: Probing to minimize. arXiv preprint arXiv:2111.01955 (2021)"},{"issue":"6684","key":"9_CR30","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684), 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-18367-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T07:29:16Z","timestamp":1728199756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-18367-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031183669","9783031183676"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-18367-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Potsdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2022.eu\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"57% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}