{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:08:12Z","timestamp":1743070092775,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819628445"},{"type":"electronic","value":"9789819628452"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-2845-2_25","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:23Z","timestamp":1740067223000},"page":"393-408","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Contention Resolution Schemes for\u00a0Size-Stochastic Knapsacks"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-4725-1501","authenticated-orcid":false,"given":"Toru","family":"Yoshinaga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5626-779X","authenticated-orcid":false,"given":"Yasushi","family":"Kawase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., W\u0142odarczyk, M.: Random order contention resolution schemes. In: Proceedings of the 59th Annual Symposium on Foundations of Computer Science, pp. 790\u2013801 (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1137\/120878422","volume":"43","author":"S Alaei","year":"2014","unstructured":"Alaei, S.: Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers. SIAM J. Comput. 43(2), 930\u2013972 (2014)","journal-title":"SIAM J. Comput."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M.T., Liaghat, V.: The online stochastic generalized assignment problem. In: Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 11\u201325 (2013)","DOI":"10.1007\/978-3-642-40328-6_2"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1647\u20131665 (2011)","DOI":"10.1137\/1.9781611973082.127"},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/nav.3220400203","volume":"40","author":"RL Carraway","year":"1993","unstructured":"Carraway, R.L., Schmidt, R.L., Weatherford, L.R.: An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Nav. Res. Logist. 40(2), 161\u2013173 (1993)","journal-title":"Nav. Res. Logist."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Chawla, S., Miller, J.B.: Mechanism design for subadditive agents via an ex ante relaxation. In: Proceedings of the 17th ACM Conference on Economics and Computation, pp. 579\u2013596 (2016)","DOI":"10.1145\/2940716.2940756"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"De, A.: Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1286\u20131305 (2018)","DOI":"10.1137\/1.9781611975031.84"},{"issue":"4","key":"25_CR9","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."},{"key":"25_CR10","unstructured":"Dughmi, S.: Matroid secretary is equivalent to contention resolution. In: Proceedings of the 13th Innovations in Theoretical Computer Science Conference, vol.\u00a0215, pp. 58:1\u201358:23 (2022)"},{"issue":"3","key":"25_CR11","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/20M1323850","volume":"49","author":"P D\u00fctting","year":"2020","unstructured":"D\u00fctting, P., Feldman, M., Kesselheim, T., Lucier, B.: Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3), 540\u2013582 (2020)","journal-title":"SIAM J. Comput."},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In: Proceedings of the 21st ACM Conference on Economics and Computation, pp. 769\u2013787 (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: Proceedings of the 5th Workshop of Internet and Network Economics, pp. 374\u2013385 (2009)","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1014\u20131033 (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"issue":"2","key":"25_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/18M1226130","volume":"50","author":"M Feldman","year":"2021","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2), 255\u2013300 (2021)","journal-title":"SIAM J. Comput."},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Feng, Y., Niazadeh, R., Saberi, A.: Near-optimal Bayesian online assortment of reusable resources. In: Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 964\u2013965 (2022)","DOI":"10.1145\/3490486.3538320"},{"key":"25_CR17","unstructured":"Fu, H., Tang, Z.G., Wu, H., Wu, J., Zhang, Q.: Random order vertex arrival contention resolution schemes for matching, with applications. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, pp. 68:1\u201368:20 (2021)"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 827\u2013836 (2011)","DOI":"10.1109\/FOCS.2011.48"},{"key":"25_CR19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.tcs.2014.10.017","volume":"562","author":"X Han","year":"2015","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theoret. Comput. Sci. 562, 395\u2013405 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Jiang, J., Ma, W., Zhang, J.: Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In: Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1221\u20131246 (2022)","DOI":"10.1137\/1.9781611977073.51"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Rabani, Y., Tardos, \u00c9.: Allocating bandwidth for bursty connections. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 664\u2013673 (1997)","DOI":"10.1145\/258533.258661"},{"key":"25_CR22","unstructured":"Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: Proceedings of the 26th Annual European Symposium on Algorithms, pp. 57:1\u201357:14 (2018)"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"MacRury, C., Ma, W., Grammel, N.: On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. Oper. Res. (2024)","DOI":"10.1287\/opre.2023.0339"},{"issue":"1\u20133","key":"25_CR24","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01585758","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68(1\u20133), 73\u2013104 (1995)","journal-title":"Math. Program."},{"issue":"5","key":"25_CR25","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5), 22\u201331 (2007)","journal-title":"J. ACM"},{"issue":"12","key":"25_CR26","doi-asserted-by":"publisher","first-page":"1706","DOI":"10.1287\/mnsc.42.12.1706","volume":"42","author":"JD Papastavrou","year":"1996","unstructured":"Papastavrou, J.D., Rajagopalan, S., Kleywegt, A.J.: The dynamic and stochastic knapsack problem with deadlines. Manag. Sci. 42(12), 1706\u20131718 (1996)","journal-title":"Manag. Sci."},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Yang, S., Khuller, S., Choudhary, S., Mitra, S., Mahadik, K.: Correlated stochastic knapsack with a submodular objective. In: Proceedings of the 30th Annual European Symposium on Algorithms, ESA 2022, pp. 91:1\u201391:14 (2022)","DOI":"10.1145\/3492323.3495594"},{"key":"25_CR28","unstructured":"Yoshinaga, T., Kawase, Y.: Size-stochastic knapsack online contention resolution schemes. arXiv preprint arXiv:2305.08622 (2023)"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Naroditskiy, V.: Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding. In: Proceedings of the 17th International Conference on World Wide Web, pp. 1175\u20131176 (2008)","DOI":"10.1145\/1367497.1367713"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-2845-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:31Z","timestamp":1740067231000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-2845-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819628445","9789819628452"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-2845-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"21 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/walcom2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}