{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T20:05:19Z","timestamp":1778270719326,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,4,27]],"date-time":"2020-04-27T00:00:00Z","timestamp":1587945600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,27]],"date-time":"2020-04-27T00:00:00Z","timestamp":1587945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1010789"],"award-info":[{"award-number":["CNS-1010789"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422569"],"award-info":[{"award-number":["CCF-1422569"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1749864"],"award-info":[{"award-number":["CCF-1749864"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00453-020-00698-3","type":"journal-article","created":{"date-parts":[[2020,4,27]],"date-time":"2020-04-27T02:02:28Z","timestamp":1587952948000},"page":"2737-2783","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Online Stochastic Matching: New Algorithms and Bounds"],"prefix":"10.1007","volume":"82","author":[{"given":"Brian","family":"Brubach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthik Abinav","family":"Sankararaman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,27]]},"reference":[{"key":"698_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1253\u20131264. SIAM (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"698_CR2","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M.T., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 18\u201335. ACM (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"698_CR3","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M.T., Liaghat, V.: The online stochastic generalized assignment problem. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 11\u201325. Springer (2013)","DOI":"10.1007\/978-3-642-40328-6_2"},{"key":"698_CR4","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: The stochastic matching problem with (very) few queries. In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 43\u201360. ACM (2016)","DOI":"10.1145\/2940716.2940769"},{"key":"698_CR5","unstructured":"Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: Attenuate locally, win globally: an attenuation-based framework for online stochastic matching with timeouts. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS \u201917, pp. 1223\u20131231. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2017)"},{"key":"698_CR6","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71\u201378. ACM (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"698_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: Proceedings of the 12th ACM Conference on Electronic Commerce, pp. 29\u201338. ACM 2011","DOI":"10.1145\/1993574.1993581"},{"key":"698_CR8","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Sivan, B., Azar, Y.: Asymptotically optimal algorithm for stochastic adwords. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 388\u2013404. ACM (2012)","DOI":"10.1145\/2229012.2229043"},{"key":"698_CR9","doi-asserted-by":"crossref","unstructured":"Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: Internet and Network Economics, pp. 374\u2013385. Springer (2009)","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"698_CR10","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: beating 1-1\/e. In: Foundations of Computer Science (FOCS), pp. 117\u2013126. IEEE (2009)","DOI":"10.1109\/FOCS.2009.72"},{"issue":"3","key":"698_CR11","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM (JACM) 53(3), 324\u2013360 (2006)","journal-title":"J. ACM (JACM)"},{"key":"698_CR12","first-page":"170","volume-title":"Internet and Network Economics, Volume 7090 of Lecture Notes in Computer Science","author":"Bernhard Haeupler","year":"2011","unstructured":"Haeupler, Bernhard, Mirrokni, Vahab S., Zadimoghaddam, Morteza: Online stochastic weighted matching: improved approximation algorithms. Internet and Network Economics, Volume 7090 of Lecture Notes in Computer Science, pp. 170\u2013181. Springer, Berlin (2011)"},{"issue":"3","key":"698_CR13","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1287\/moor.2013.0621","volume":"39","author":"P Jaillet","year":"2013","unstructured":"Jaillet, P., Lu, X.: Online stochastic matching: new algorithms with better bounds. Math. Oper. Res. 39(3), 624\u2013646 (2013)","journal-title":"Math. Oper. Res."},{"key":"698_CR14","doi-asserted-by":"crossref","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Automata, Languages and Programming, pp. 508\u2013520. Springer (2009)","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"698_CR15","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: European Symposium on Algorithms (ESA), pp. 589\u2013600. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"698_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 352\u2013358. ACM (1990)","DOI":"10.1145\/100216.100262"},{"key":"698_CR17","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A.: Efficient inverse maintenance and faster algorithms for linear programming. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 230\u2013249. IEEE (2015)","DOI":"10.1109\/FOCS.2015.23"},{"issue":"4","key":"698_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2012","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2012)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"4","key":"698_CR19","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559\u2013573 (2012)","journal-title":"Math. Oper. Res."},{"key":"698_CR20","doi-asserted-by":"crossref","unstructured":"Mehta, A., Panigrahi, D.: Online matching with stochastic rewards. In: Foundations of Computer Science (FOCS), pp. 728\u2013737. IEEE (2012)","DOI":"10.1109\/FOCS.2012.65"},{"key":"698_CR21","doi-asserted-by":"crossref","unstructured":"Mehta, A., Waggoner, B., Zadimoghaddam, M.: Online stochastic matching with unequal probabilities. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2015)","DOI":"10.1137\/1.9781611973730.92"},{"key":"698_CR22","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. ACM (2011)","DOI":"10.1145\/1993636.1993716"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00698-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00698-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00698-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T00:05:18Z","timestamp":1619481918000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00698-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,27]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["698"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00698-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,27]]},"assertion":[{"value":"19 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}