{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T23:09:08Z","timestamp":1778454548789,"version":"3.51.4"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032186591","type":"print"},{"value":"9783032186607","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-18660-7_36","type":"book-chapter","created":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T22:27:21Z","timestamp":1778452041000},"page":"669-685","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New Concentration Bounds and\u00a0Their Applications in\u00a0Online Resource Allocation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3427-9014","authenticated-orcid":false,"given":"Jinshan","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4098-844X","authenticated-orcid":false,"given":"Biaoshuai","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5330-5514","authenticated-orcid":false,"given":"Nan","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6335-8312","authenticated-orcid":false,"given":"Meng","family":"Xi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3564-1628","authenticated-orcid":false,"given":"Tao","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4703-7348","authenticated-orcid":false,"given":"Jianwei","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,1]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1405\u20131424. SIAM (2015)","DOI":"10.1137\/1.9781611973730.93"},{"issue":"4","key":"36_CR2","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014)","journal-title":"Oper. Res."},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"Albers, S., Janke, M.: Scheduling in the random-order model. Algorithmica, 1\u201330 (2021)","DOI":"10.1007\/s00453-021-00841-8"},{"key":"36_CR4","unstructured":"Albers, S., Janke, M.: Scheduling in the secretary model. In: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, p.\u00a01 (2021)"},{"issue":"6","key":"36_CR5","doi-asserted-by":"publisher","first-page":"1750","DOI":"10.1007\/s00453-021-00801-2","volume":"83","author":"S Albers","year":"2021","unstructured":"Albers, S., Khan, A., Ladewig, L.: Improved online algorithms for knapsack and gap in the random order model. Algorithmica 83(6), 1750\u20131785 (2021)","journal-title":"Algorithmica"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Albers, S., G\u00e1lvez, W., Janke, M.: Machine covering in the random-order model. Algorithmica, 1\u201326 (2022)","DOI":"10.1007\/s00453-022-01011-0"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pp. 32\u201340. IEEE (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"issue":"2","key":"36_CR8","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"36_CR9","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.ejor.2015.06.029","volume":"247","author":"Xiao Alison Chen and Zizhuo Wang","year":"2015","unstructured":"Xiao Alison Chen and Zizhuo Wang: A dynamic learning algorithm for online matching problems with concave returns. Eur. J. Oper. Res. 247(2), 379\u2013388 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 137\u2013144 (2012)","DOI":"10.1145\/2213977.2213992"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Freedman, D.A.: On tail probabilities for martingales. Ann. Probab., 100\u2013118 (1975)","DOI":"10.1214\/aop\/1176996452"},{"issue":"1","key":"36_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/rsa.20532","volume":"47","author":"D Gavinsky","year":"2015","unstructured":"Gavinsky, D., Lovett, S., Saks, M., Srinivasan, S.: A tail bound for read-k families of functions. Random Struct. Algorithms 47(1), 99\u2013108 (2015)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"36_CR13","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1287\/moor.2016.0782","volume":"41","author":"A Gupta","year":"2016","unstructured":"Gupta, A., Molinaro, M.: How the experts algorithm can help solve LPs online. Math. Oper. Res. 41(4), 1404\u20131431 (2016)","journal-title":"Math. Oper. Res."},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kehne, G., Levin, R.: Random order online set cover is as easy as offline. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 1253\u20131264. IEEE (2022)","DOI":"10.1109\/FOCS52979.2021.00122"},{"key":"36_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1214\/18-PS321","volume":"17","author":"SR Howard","year":"2020","unstructured":"Howard, S.R., Ramdas, A., McAuliffe, J., Sekhon, J.: Time-uniform Chernoff bounds via nonnegative supermartingales. Probab. Surv. 17, 257\u2013317 (2020)","journal-title":"Probab. Surv."},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhang, Q., Zhang, Y.: Adwords in a panorama. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 1416\u20131426. IEEE (2020)","DOI":"10.1109\/FOCS46700.2020.00133"},{"issue":"5","key":"36_CR17","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/15M1033708","volume":"47","author":"T Kesselheim","year":"2018","unstructured":"Kesselheim, T., Radke, K., Tonnis, A., Vocking, B.: Primal beats dual on online packing LPs in the random-order model. SIAM J. Comput. 47(5), 1939\u20131964 (2018)","journal-title":"SIAM J. Comput."},{"key":"36_CR18","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 630\u2013631. Citeseer (2005)"},{"key":"36_CR19","doi-asserted-by":"crossref","unstructured":"Klimm, M., Knaack, M.: Generalized assignment and knapsack problems in the random-order model. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 341\u2013354. Springer (2025)","DOI":"10.1007\/978-3-031-93112-3_25"},{"key":"36_CR20","unstructured":"Kuszmaul, W., Qi, Q.: The multiplicative version of Azuma\u2019s inequality, with an application to contention analysis. arXiv preprint: arXiv:2102.05077 (2025)"},{"key":"36_CR21","unstructured":"Lampert, C.H., Ralaivola, L., Zimin, A.: Dependency-dependent bounds for sums of dependent random variables. arXiv preprint: arXiv:1811.01404 (2018)"},{"key":"36_CR22","unstructured":"Li, S., Liu, Y.: Concentration inequalities for general functions of heavy-tailed random variables. In: Forty-First International Conference on Machine Learning (ICML24) (2024)"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Designing networks incrementally. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 406\u2013415. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959915"},{"key":"36_CR25","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 426\u2013431. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"issue":"1","key":"36_CR26","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1287\/moor.2013.0612","volume":"39","author":"M Molinaro","year":"2014","unstructured":"Molinaro, M., Ravi, R.: The geometry of online packing linear programs. Math. Oper. Res. 39(1), 46\u201359 (2014)","journal-title":"Math. Oper. Res."},{"key":"36_CR27","doi-asserted-by":"crossref","unstructured":"Molinaro, M.: Online and random-order load balancing simultaneously. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1638\u20131650. SIAM (2017)","DOI":"10.1137\/1.9781611974782.108"},{"issue":"2","key":"36_CR28","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26(2), 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"36_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00009-017-1043-2","volume":"14","author":"C Pelekis","year":"2017","unstructured":"Pelekis, C., Ramon, J.: Hoeffding\u2019s inequality for sums of dependent random variables. Mediterr. J. Math. 14, 1\u201316 (2017)","journal-title":"Mediterr. J. Math."},{"key":"36_CR30","doi-asserted-by":"crossref","unstructured":"Peng, B., Tang, Z.G.: Revisiting ranking for online bipartite matching with random arrivals: the primal-dual analysis. In: Proceedings of the 26th ACM Conference on Economics and Computation, pp. 820\u2013835 (2025)","DOI":"10.1145\/3736252.3742631"},{"issue":"6","key":"36_CR31","doi-asserted-by":"publisher","first-page":"1811","DOI":"10.1090\/S0002-9939-98-04254-3","volume":"126","author":"A Pruss","year":"1998","unstructured":"Pruss, A.: A maximal inequality for partial sums of finite exchangeable sequences of random variables. Proc. Am. Math. Soc. 126(6), 1811\u20131819 (1998)","journal-title":"Proc. Am. Math. Soc."},{"key":"36_CR32","doi-asserted-by":"crossref","unstructured":"Raginsky, M., Sason, I., et\u00a0al.: Concentration of measure inequalities in information theory, communications, and coding. Found. Trends\u00ae Commun. Inf. Theory 10(1\u20132), 1\u2013246 (2013)","DOI":"10.1561\/0100000064"},{"key":"36_CR33","doi-asserted-by":"crossref","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff\u2013Hoeffding bounds for applications with limited independence. SIAM J. Discr. Math. 8(2), 223\u2013250 (1995)","DOI":"10.1137\/S089548019223872X"},{"issue":"1","key":"36_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.3934\/puqr.2021003","volume":"6","author":"Y Tanoue","year":"2021","unstructured":"Tanoue, Y.: Improved Hoeffding inequality for dependent bounded or sub-gaussian random variables. Probab., Uncertainty Quant. Risk 6(1), 53\u201360 (2021)","journal-title":"Probab., Uncertainty Quant. Risk"},{"key":"36_CR35","unstructured":"Udwani, R.: Adwords with unknown budgets. arXiv preprint: arXiv:2110.00504 (2021)"},{"key":"36_CR36","doi-asserted-by":"crossref","unstructured":"van de Geer, S.A.: On Hoeffding\u2019s inequality for dependent random variables. In: Empirical Process Techniques for Dependent Data, pp. 161\u2013169. Springer (2002)","DOI":"10.1007\/978-1-4612-0099-4_4"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-18660-7_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T22:27:24Z","timestamp":1778452044000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-18660-7_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032186591","9783032186607"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-18660-7_36","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":"1 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New Brunswick, NJ","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","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":"8 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2025.cs.rutgers.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}