{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T02:11:53Z","timestamp":1777342313489,"version":"3.51.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,8,27]],"date-time":"2018-08-27T00:00:00Z","timestamp":1535328000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1585\/15"],"award-info":[{"award-number":["1585\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014414"],"award-info":[{"award-number":["2014414"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["148\/16"],"award-info":[{"award-number":["148\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0505-7","type":"journal-article","created":{"date-parts":[[2018,8,27]],"date-time":"2018-08-27T09:17:40Z","timestamp":1535361460000},"page":"1781-1799","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Online Algorithms for Maximum Cardinality Matching with Edge Arrivals"],"prefix":"10.1007","volume":"81","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4684-2185","authenticated-orcid":false,"given":"Danny","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yevgeny","family":"Tkach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,27]]},"reference":[{"key":"505_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 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"505_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Cohen, I.R., Roytman, A.: Online lower bounds via duality. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038\u20131050 (2017)","DOI":"10.1137\/1.9781611974782.66"},{"key":"505_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Jain, K., Naor, J.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Proceedings of the 15th Annual European Symposium on Algorithms, pp. 253\u2013264 (2007)","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"505_CR4","doi-asserted-by":"crossref","unstructured":"Chiplunkar, A., Tirodkar, S., Vishwanathan, S.: On randomized algorithms for matching in the online preemptive model. In: Proceedings of the 23rd Annual European Symposium on Algorithms, pp. 325\u2013336 (2015)","DOI":"10.1007\/978-3-662-48350-3_28"},{"key":"505_CR5","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 10th ACM Conference on Electronic Commerce, pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"505_CR6","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th ACM Symposium on Theory of Computing, pp. 137\u2013144 (2012)","DOI":"10.1145\/2213977.2213992"},{"key":"505_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"issue":"1","key":"505_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.ic.2017.12.002","volume":"259","author":"L Epstein","year":"2018","unstructured":"Epstein, L., Levin, A., Segev, D., Weimann, O.: Improved bounds for randomized preemptive online matching. Inf. Comput. 259(1), 31\u201340 (2018)","journal-title":"Inf. Comput."},{"key":"505_CR9","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online stochastic matching: Beating \n                    \n                      \n                    \n                    $$1-1\/e$$\n                    \n                      \n                        \n                          1\n                          -\n                          1\n                          \/\n                          e\n                        \n                      \n                    \n                  . In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 117\u2013126 (2009)","DOI":"10.1109\/FOCS.2009.72"},{"key":"505_CR10","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 982\u2013991 (2008)"},{"key":"505_CR11","doi-asserted-by":"crossref","unstructured":"Guruganesh, G.P., Singla, S.: Online matroid intersection: beating half for random arrival. In: Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization, pp. 241\u2013253 (2017)","DOI":"10.1007\/978-3-319-59250-3_20"},{"issue":"1\u20132","key":"505_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1\u20132), 319\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"505_CR13","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 587\u2013596 (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"505_CR14","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 22nd Annual ACM Symposium on Theory of Computing, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"505_CR15","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 43rd ACM Symposium on Theory of Computing, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"505_CR16","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."},{"issue":"4","key":"505_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"5","key":"505_CR18","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.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007)","journal-title":"J. ACM"},{"key":"505_CR19","doi-asserted-by":"crossref","unstructured":"Tirodkar, S., Vishwanathan, S.: Maximum matching on trees in the online preemptive and the incremental dynamic graph models. In: Proceedings of the 23rd International Conference on Computing and Combinatorics, pp. 504\u2013515 (2017)","DOI":"10.1007\/978-3-319-62389-4_42"},{"key":"505_CR20","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wong, S.C.: Two-sided online bipartite matching and vertex cover: beating the greedy algorithm. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, pp. 1070\u20131081 (2015)","DOI":"10.1007\/978-3-662-47672-7_87"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0505-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0505-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0505-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,22]],"date-time":"2019-09-22T15:45:46Z","timestamp":1569167146000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0505-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,27]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["505"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0505-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,27]]},"assertion":[{"value":"18 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}