{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T09:33:54Z","timestamp":1763544834813},"publisher-location":"Cham","reference-count":20,"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_20","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"241-253","source":"Crossref","is-referenced-by-count":10,"title":["Online Matroid Intersection: Beating Half for Random Arrival"],"prefix":"10.1007","author":[{"given":"Guru Prashanth","family":"Guruganesh","sequence":"first","affiliation":[]},{"given":"Sahil","family":"Singla","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/rsa.3240060107","volume":"6","author":"J Aronson","year":"1995","unstructured":"Aronson, J., Dyer, M., Frieze, A., Suen, S.: Randomized greedy matching. II. Random Struct. Algorithms 6(1), 55\u201373 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Quanrud, K.: Fast approximations for matroid intersection. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (2016)","DOI":"10.1137\/1.9781611974331.ch33"},{"key":"20_CR3","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and Their Applications, pp. 69\u201387 (1970)"},{"issue":"3","key":"20_CR4","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math. 25(3), 1251\u20131265 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR5","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 (2008)"},{"issue":"4","key":"20_CR6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Huang, C.-C., Kakimura, N., Kamiyama, N.: Exact and approximation algorithms for weighted matroid intersection. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch32"},{"key":"20_CR8","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":"20_CR9","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"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-32512-0_20","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C Konrad","year":"2012","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM -2012. LNCS, vol. 7408, pp. 231\u2013242. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-32512-0_20"},{"key":"20_CR11","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization","author":"B Korte","year":"2008","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization. Algorithms and Combinatorics, vol. 21. Springer, Berlin (2008)"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Korula, N., Mirrokni, V., Zadimoghaddam, M.: Online submodular welfare maximization: greedy beats 1\/2 in random order. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 889\u2013898 (2015)","DOI":"10.1145\/2746539.2746626"},{"key":"20_CR13","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: 10.1007\/978-3-642-02930-1_42"},{"key":"20_CR14","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":"20_CR15","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":"20_CR16","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)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Mehta, A., Vazirani, V.: Personal communication (2015)","DOI":"10.1016\/B978-0-12-800939-0.00014-0"},{"key":"20_CR18","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, Oxford (2006)"},{"key":"20_CR19","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Heidelberg (2002)"},{"key":"20_CR20","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: 10.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_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T16:31:14Z","timestamp":1659025874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}