{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:06:35Z","timestamp":1760709995873,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T00:00:00Z","timestamp":1567814400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T00:00:00Z","timestamp":1567814400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["1760102"],"award-info":[{"award-number":["1760102"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00224-019-09947-7","type":"journal-article","created":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T01:03:06Z","timestamp":1567818186000},"page":"645-661","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals"],"prefix":"10.1007","volume":"64","author":[{"given":"Minjun","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorit S.","family":"Hochbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quico","family":"Spaen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1176-5159","authenticated-orcid":false,"given":"Mark","family":"Velednitsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,7]]},"reference":[{"issue":"2","key":"9947_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.ejor.2012.05.028","volume":"223","author":"N Agatz","year":"2012","unstructured":"Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Optimization for dynamic ride-sharing: A review. Eur. J. Oper. Res. 223(2), 295\u2013303 (2012)","journal-title":"Eur. J. Oper. Res."},{"issue":"6","key":"9947_CR2","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1111\/j.1937-5956.2007.tb00288.x","volume":"16","author":"Z Aksin","year":"2007","unstructured":"Aksin, Z., Armony, M., Mehrotra, V.: The modern call center: A multi-disciplinary perspective on operations management research. Prod. Oper. Manag. 16(6), 665\u2013688 (2007)","journal-title":"Prod. Oper. Manag."},{"key":"9947_CR3","doi-asserted-by":"publisher","unstructured":"Bansal, N., Buchbinder, N., Gupta, A., Naor, J. S.: An $O(\\log ^{2} k)$-competitive algorithm for metric bipartite matching. In: European symposium on algorithms. pp. 522\u2013533. Springer (2007), \nhttps:\/\/doi.org\/10.1007\/978-3-540-75520-3_47","DOI":"10.1007\/978-3-540-75520-3_47"},{"key":"9947_CR4","doi-asserted-by":"publisher","unstructured":"Brubach, B., Sankararaman, K. A., Srinivasan, A., Xu, P.: New algorithms, better bounds, and a novel model for online stochastic matching. In: 24th annual European symposium on algorithms. vol. 57, pp. 24:1\u201324:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016), \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.24","DOI":"10.4230\/LIPIcs.ESA.2016.24"},{"key":"9947_CR5","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Cohen, M. B., Lee, Y. T., Lee, J. R., Madry, A.: K-server via multiscale entropic regularization. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing. pp. 3\u201316. ACM (2018), \nhttps:\/\/doi.org\/10.1145\/3188745.3188798","DOI":"10.1145\/3188745.3188798"},{"key":"9947_CR6","doi-asserted-by":"publisher","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM conference on economics and computation. pp. 169\u2013186. ACM (2017), \nhttps:\/\/doi.org\/10.1145\/3033274.3085137","DOI":"10.1145\/3033274.3085137"},{"key":"9947_CR7","unstructured":"Dehghani, S., Ehsani, S., Hajiaghayi, M., Liaghat, V., Seddighin, S.: Stochastic k-server: How should uber work?. In: 44th international colloquium on automata, languages, and programming. vol. 80, pp. 126:1\u2013126:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)"},{"key":"9947_CR8","doi-asserted-by":"publisher","unstructured":"Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: International workshop on internet and network economics. pp. 374\u2013385. Springer (2009), \nhttps:\/\/doi.org\/10.1007\/978-3-642-10841-9_34","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"9947_CR9","doi-asserted-by":"publisher","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1-1\/e. In: 50th annual IEEE symposium on foundations of computer science. pp. 117\u2013126. IEEE (2009), \nhttps:\/\/doi.org\/10.1109\/FOCS.2009.72","DOI":"10.1109\/FOCS.2009.72"},{"key":"9947_CR10","doi-asserted-by":"publisher","unstructured":"Haeupler, B., Mirrokni, V. S., Zadimoghaddam, M.: Online stochastic weighted matching: Improved approximation algorithms. In: International workshop on internet and network economics. pp. 170\u2013181. Springer (2011), \nhttps:\/\/doi.org\/10.1007\/978-3-642-25510-6_15","DOI":"10.1007\/978-3-642-25510-6_15"},{"issue":"3","key":"9947_CR11","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993). \nhttps:\/\/doi.org\/10.1006\/jagm.1993.1026","journal-title":"J. Algorithms"},{"key":"9947_CR12","doi-asserted-by":"publisher","unstructured":"Karp, R. M., Vazirani, U. V., Vazirani, V. V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd annual ACM symposium on theory of computing. pp. 352\u2013358. ACM (1990), \nhttps:\/\/doi.org\/10.1145\/100216.100262","DOI":"10.1145\/100216.100262"},{"key":"9947_CR13","doi-asserted-by":"publisher","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. pp. 589\u2013600. Springer (2013), \nhttps:\/\/doi.org\/10.1007\/978-3-642-40450-4_50","DOI":"10.1007\/978-3-642-40450-4_50"},{"issue":"2","key":"9947_CR14","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S. G., Vazirani, V. V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994). \nhttps:\/\/doi.org\/10.1016\/0304-3975(94)90042-6","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9947_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009). \nhttps:\/\/doi.org\/10.1016\/j.cosrev.2009.04.002","journal-title":"Comput. Sci. Rev."},{"key":"9947_CR16","doi-asserted-by":"publisher","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of the 43rd annual ACM symposium on Theory of computing. pp. 597\u2013606. ACM (2011), \nhttps:\/\/doi.org\/10.1145\/1993636.1993716","DOI":"10.1145\/1993636.1993716"},{"issue":"2","key":"9947_CR17","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M. S., McGeoch, L. A., Sleator, D. D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990). \nhttps:\/\/doi.org\/10.1016\/0196-6774(90)90003-W","journal-title":"J. Algorithms"},{"issue":"4","key":"9947_CR18","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). \nhttps:\/\/doi.org\/10.1287\/moor.1120.0551","journal-title":"Math. Oper. Res."},{"issue":"4","key":"9947_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A., et al.: Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science 8(4), 265\u2013368 (2013). \nhttps:\/\/doi.org\/10.1561\/0400000057","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"9947_CR20","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms. pp. 954\u2013959. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109662"},{"key":"9947_CR21","doi-asserted-by":"publisher","unstructured":"Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques. vol. 60, pp. 18:1\u201318:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016), \nhttps:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.18","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.18"},{"key":"9947_CR22","doi-asserted-by":"crossref","unstructured":"Ross, S. M.: Introduction to probability models. Academic press (2014)","DOI":"10.1016\/B978-0-12-407948-9.00001-3"},{"issue":"3","key":"9947_CR23","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1287\/opre.1040.0180","volume":"53","author":"X Su","year":"2005","unstructured":"Su, X., Zenios, S. A.: Patient choice in kidney allocation: A sequential stochastic assignment model. Oper. Res. 53(3), 443\u2013455 (2005)","journal-title":"Oper. Res."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09947-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09947-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09947-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T23:39:47Z","timestamp":1599349187000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09947-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,7]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["9947"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09947-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2019,9,7]]},"assertion":[{"value":"7 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}