{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:36Z","timestamp":1781305056885,"version":"3.54.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_27","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:13Z","timestamp":1781303713000},"page":"410-425","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bayesian Probing on\u00a0Graphs"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rudy","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"27_CR1","first-page":"16903","volume":"33","author":"G Amanatidis","year":"2020","unstructured":"Amanatidis, G., Fusco, F., Lazos, P., Leonardi, S., Reiffenh\u00e4user, R.: Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. Adv. Neural. Inf. Process. Syst. 33, 16903\u201316915 (2020)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Boswell, G.P., Britton, N.F., Franks, N.R.: Habitat fragmentation, percolation theory and the conservation of a keystone species. Proc. Royal Soc. London. Ser. B Biol. Sci. 265(1409), 1921\u20131925 (1998)","DOI":"10.1098\/rspb.1998.0521"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Cai, Y., Oikonomou, A.: On simple mechanisms for dependent items. In: Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 242\u2013262(2021)","DOI":"10.1145\/3465456.3467643"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Chawla, S., Gergatsouli, E., Teng, Y., Tzamos, C., Zhang, R.: Pandora\u2019s box withcorrelations: Learning and approximation. In: 2020 IEEE 61st Annual Symposiumon Foundations of Computer Science (FOCS), pp. 1214\u20131225. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00116"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Cui, Y., Nagarajan, V.: Minimum cost adaptive submodular cover. In: Symposiumon Simplicity in Algorithms (SOSA), pp. 12\u201327. SIAM (2023)","DOI":"10.1137\/1.9781611977585.ch2"},{"issue":"7204","key":"27_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1038\/nature07053","volume":"454","author":"S Davis","year":"2008","unstructured":"Davis, S., Trapman, P., Leirs, H., Begon, M., Heesterbeek, J.: The abundance threshold for plague as a critical percolation phenomenon. Nature 454(7204), 634\u2013637 (2008)","journal-title":"Nature"},{"key":"27_CR7","doi-asserted-by":"crossref","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)","DOI":"10.1287\/moor.1080.0330"},{"key":"27_CR8","unstructured":"Esfandiari, H., Karbasi, A., Mirrokni, V.: Adaptivity in adaptive submodularity. In: Conference on Learning Theory, pp. 1823\u20131846. PMLR (2021)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Garnett, R.: Bayesian Optimization. Cambridge University Press (2023)","DOI":"10.1017\/9781108348973"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"Garnett, R., G\u00e4rtner, T., Vogt, M., Bajorath, J.: Introducing the \u201cactive search\u201d method for iterative virtual screening. J. Comput. Aided Mol. Des. 29(4), 305\u2013314 (2015)","DOI":"10.1007\/s10822-015-9832-9"},{"key":"27_CR11","unstructured":"Garnett, R., Krishnamurthy, Y., Xiong, X., Schneider, J.G., Mann, R.P.: Bayesian optimal active search and surveying. In: Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012. icml.cc \/ Omnipress (2012). http:\/\/icml.cc\/2012\/papers\/618.pdf"},{"key":"27_CR12","doi-asserted-by":"publisher","unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427\u2013486 (2011). https:\/\/doi.org\/10.1613\/JAIR.3278","DOI":"10.1613\/JAIR.3278"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Grimmett, G.R., Stacey, A.M.: Critical probabilities for site and bond percolation models. Ann. Probab. 26(4), 1788\u20131812 (1998). http:\/\/www.jstor.org\/stable\/2652790","DOI":"10.1214\/aop\/1022855883"},{"key":"27_CR14","doi-asserted-by":"publisher","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, pp. 827\u2013836. IEEE Computer Society (2011). https:\/\/doi.org\/10.1109\/FOCS.2011.48","DOI":"10.1109\/FOCS.2011.48"},{"key":"27_CR15","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":"27_CR16","doi-asserted-by":"publisher","unstructured":"Gupta, A., Nagarajan, V., Singla, S.: Algorithms and adaptivity gaps for stochastic probing. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1731\u20131747. SIAM (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.CH120","DOI":"10.1137\/1.9781611974331.CH120"},{"key":"27_CR17","doi-asserted-by":"publisher","unstructured":"Gupta, A., Nagarajan, V., Singla, S.: Adaptivity gaps for stochastic probing: Submodular and XOS functions. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 1688\u20131702. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.111","DOI":"10.1137\/1.9781611974782.111"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1613\/jair.1.12368","volume":"71","author":"L Hellerstein","year":"2021","unstructured":"Hellerstein, L., Kletenik, D., Parthasarathy, S.: A tight bound for stochastic submodular cover. J. Artif. Intell. Res. 71, 347\u2013370 (2021)","journal-title":"J. Artif. Intell. Res."},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","DOI":"10.1145\/321906.321909"},{"key":"27_CR20","unstructured":"Jiang, S., Malkomes, G., Abbott, M., Moseley, B., Garnett, R.: Efficient nonmyopic batch active search. In: Bengio, S., Wallach, H.M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada, pp. 1107\u20131117 (2018). https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/a7aeed74714116f3b292a982238f83d2-Abstract.html"},{"key":"27_CR21","unstructured":"Jiang, S., Malkomes, G., Converse, G., Shofner, A., Moseley, B., Garnett, R.: Efficient nonmyopic active search. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017. Proceedings of Machine Learning Research, vol.\u00a070, pp. 1714\u20131723. PMLR (2017). http:\/\/proceedings.mlr.press\/v70\/jiang17d.html"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Krivelevich, M.: The phase transition in site percolation on pseudo-random graphs. Electron. J. Comb. 22, \u00a0P00 (2015)","DOI":"10.37236\/5392"},{"key":"27_CR23","doi-asserted-by":"crossref","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979)","DOI":"10.1287\/moor.4.4.339"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Livanos, V., Patton, K., Singla, S.: Improved mechanisms and prophet inequalities for graphical dependencies. In: Proceedings of the 25th ACM Conference on Economics and Computation, pp. 782\u2013805 (2024)","DOI":"10.1145\/3670865.3673462"},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and markovian bandits approximation algorithms. Math. Oper. Res. 43(3), 789\u2013812 (2018)","DOI":"10.1287\/moor.2017.0884"},{"key":"27_CR26","doi-asserted-by":"crossref","unstructured":"Reidys, C.M.: Large components in random induced subgraphs of n-cubes. Discret. Math. 309(10), 3113\u20133124 (2009)","DOI":"10.1016\/j.disc.2008.08.015"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.tcs.2022.09.022","volume":"936","author":"S Tang","year":"2022","unstructured":"Tang, S.: Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and k-system constraints. Theoret. Comput. Sci. 936, 139\u2013147 (2022)","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR28","doi-asserted-by":"publisher","unstructured":"Wang, X., Garnett, R., Schneider, J.G.: Active search on graphs. In: Dhillon, I.S., et al. (eds.) The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11\u201314, 2013, pp. 731\u2013738. ACM (2013). https:\/\/doi.org\/10.1145\/2487575.2487605","DOI":"10.1145\/2487575.2487605"},{"key":"27_CR29","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridgeuniversity Press (2011)","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:20Z","timestamp":1781303720000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}