{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T15:32:27Z","timestamp":1767108747605},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_29","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"355-367","source":"Crossref","is-referenced-by-count":6,"title":["Maximum Matching in the Online Batch-Arrival Model"],"prefix":"10.1007","author":[{"given":"Euiwoong","family":"Lee","sequence":"first","affiliation":[]},{"given":"Sahil","family":"Singla","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching & single-bid budgeted allocations. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"issue":"5","key":"29_CR2","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/1183907.1183913","volume":"53","author":"A Blum","year":"2006","unstructured":"Blum, A., Sandholm, T., Zinkevich, M.: Online algorithms for market clearing. J. ACM (JACM) 53(5), 845\u2013879 (2006)","journal-title":"J. ACM (JACM)"},{"key":"29_CR3","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"2005","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, UK (2005)"},{"key":"29_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-75520-3_24","volume-title":"Algorithms \u2013 ESA 2007","author":"N Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253\u2013264. Springer, Heidelberg (2007). doi:\n10.1007\/978-3-540-75520-3_24"},{"key":"29_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 of the 10th ACM Conference on Electronic Commerce, pp. 71\u201378. ACM (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"29_CR6","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 Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"key":"29_CR7","unstructured":"Epstein, L., Levin, A., Segev, D., Weimann, O.: Improved bounds for online preemptive matching. In: 30th International Symposium on Theoretical Aspects of Computer Science, pp. 389\u2013399 (2013)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: beating 1\u20131\/e. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 117\u2013126. IEEE (2009)","DOI":"10.1109\/FOCS.2009.72"},{"key":"29_CR9","unstructured":"Fiat, A., Algorithms, O.: The State of the Art (LNCS) (1998)"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Goel, A., Kapralov, M., Khanna, S.: On the communication and streaming complexity of maximum bipartite matching. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 468\u2013485. SIAM (2012)","DOI":"10.1137\/1.9781611973099.41"},{"key":"29_CR11","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 982\u2013991. SIAM (2008)"},{"issue":"1\u20132","key":"29_CR12","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s10107-013-0742-0","volume":"149","author":"D Golovin","year":"2015","unstructured":"Golovin, D., Goyal, V., Polishchuk, V., Ravi, R., Sysikaski, M.: Improved approximations for two-stage min-cut and shortest path problems under uncertainty. Math. Program. 149(1\u20132), 167\u2013194 (2015)","journal-title":"Math. Program."},{"key":"29_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-642-25510-6_15","volume-title":"Internet and Network Economics","author":"B Haeupler","year":"2011","unstructured":"Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 170\u2013181. Springer, Heidelberg (2011). doi:\n10.1007\/978-3-642-25510-6_15"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 587\u2013596. ACM (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"29_CR15","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 (1990)","DOI":"10.1145\/100216.100262"},{"issue":"3","key":"29_CR16","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-\n            $$\\varepsilon $$\n          . J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-642-02930-1_42","volume-title":"Automata, Languages and Programming","author":"N Korula","year":"2009","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 508\u2013520. Springer, Heidelberg (2009). doi:\n10.1007\/978-3-642-02930-1_42"},{"key":"29_CR18","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"},{"issue":"4","key":"29_CR19","doi-asserted-by":"crossref","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":"29_CR20","first-page":"265","volume":"8","author":"A Mehta","year":"2012","unstructured":"Mehta, A.: Online matching and ad allocation. Theor. Comput. Sci. 8(4), 265\u2013368 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"29_CR21","doi-asserted-by":"crossref","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 (JACM) 54(5), 22 (2007)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"29_CR22","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1122480.1122493","volume":"37","author":"C Swamy","year":"2006","unstructured":"Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News 37(1), 33\u201346 (2006)","journal-title":"ACM SIGACT News"},{"key":"29_CR23","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer Science & Business Media, New York (2013)"},{"key":"29_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1007\/978-3-662-47672-7_87","volume-title":"Automata, Languages, and Programming","author":"Y Wang","year":"2015","unstructured":"Wang, Y., Wong, S.C.: Two-sided online bipartite matching and vertex cover: beating the greedy algorithm. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 1070\u20131081. Springer, Heidelberg (2015). doi:\n10.1007\/978-3-662-47672-7_87"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:12:49Z","timestamp":1495530769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}