{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:54Z","timestamp":1750694814199,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1942010"],"award-info":[{"award-number":["1942010"]}],"id":[{"id":"10.13039\/100000083","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":[[2024,8]]},"DOI":"10.1007\/s00224-023-10155-7","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T09:14:42Z","timestamp":1702372482000},"page":"758-772","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Bounds for Matching in Random-Order Streams"],"prefix":"10.1007","volume":"68","author":[{"given":"Aaron","family":"Bernstein","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"10155_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2012.10.006","volume":"222","author":"KJ Ahn","year":"2013","unstructured":"Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. 222, 59\u201379 (2013)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S.: Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In: Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pp. 202\u2013211 (2015)","key":"10155_CR2","DOI":"10.1145\/2755573.2755586"},{"doi-asserted-by":"crossref","unstructured":"Assadi, S., Bateni, M., Bernstein, A., Mirrokni, V.S., Stein, C.: Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 1616\u20131635 (2019)","key":"10155_CR3","DOI":"10.1137\/1.9781611975482.98"},{"unstructured":"Assadi, S., Bernstein, A.: Towards a unified theory of sparsification for matching problems. In: 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8\u20139, 2019\u2013San Diego, CA, USA, pp. 11:1\u201311:20 (2019)","key":"10155_CR4"},{"doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: On estimating maximum matching size in graph streams. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pp. 1723\u20131742 (2017)","key":"10155_CR5","DOI":"10.1137\/1.9781611974782.113"},{"unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Maximum matchings in dynamic graph streams and the simultaneous communication model. In: R. Krauthgamer (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1345\u20131364. SIAM (2016)","key":"10155_CR6"},{"doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: Automata, Languages, and Programming\u201342nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 167\u2013179 (2015)","key":"10155_CR7","DOI":"10.1007\/978-3-662-47672-7_14"},{"doi-asserted-by":"crossref","unstructured":"Bury, M., Schwiegelshohn, C.: Sublinear estimation of weighted matchings in dynamic data streams. In: Algorithms\u2013ESA 2015\u201323rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp. 263\u2013274 (2015)","key":"10155_CR8","DOI":"10.1007\/978-3-662-48350-3_23"},{"doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 1326\u20131344 (2016)","key":"10155_CR9","DOI":"10.1137\/1.9781611974331.ch92"},{"doi-asserted-by":"crossref","unstructured":"Chitnis, R.H., Cormode, G., Hajiaghayi, M.T., Monemizadeh, M.: Parameterized streaming: Maximal matching and vertex cover. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pp. 1234\u20131251 (2015)","key":"10155_CR10","DOI":"10.1137\/1.9781611973730.82"},{"unstructured":"Cormode, G., Jowhari, H., Monemizadeh, M., Muthukrishnan, S.: The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pp. 29:1\u201329:15 (2017)","key":"10155_CR11"},{"unstructured":"Crouch, M., Stubbs, D.S.: Improved streaming algorithms for weighted matching, via unweighted matching. In: APPROX\/RANDOM 2014, pp. 96\u2013104 (2014)","key":"10155_CR12"},{"unstructured":"Dark, J., Konrad, C.: Optimal lower bounds for matching and vertex cover in dynamic graph streams. In: 35th Computational Complexity Conference, CCC 2020, July 28\u201331, 2020, Saarbr\u00fccken, Germany (Virtual Conference), LIPIcs, vol. 169, pp. 30:1\u201330:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"10155_CR13"},{"issue":"3","key":"10155_CR14","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M., Onak, K.: Streaming algorithms for estimating the matching size in planar graphs and beyond. ACM Trans. Algorithms 14(4), 48:1\u201348:23 (2018)","key":"10155_CR15","DOI":"10.1145\/3230819"},{"doi-asserted-by":"crossref","unstructured":"Esfandiari, H., Hajiaghayi, M., Monemizadeh, M.: Finding large matchings in semi streaming. In: C. Domeniconi, F. Gullo, F. Bonchi, J. Domingo-Ferrer, R. Baeza-Yates, Z. Zhou, X. Wu (eds.) IEEE International Conference on Data Mining Workshops, ICDM Workshops 2016, December 12-15, 2016, Barcelona, Spain, pp. 608\u2013614. IEEE Computer Society (2016)","key":"10155_CR16","DOI":"10.1109\/ICDMW.2016.0092"},{"doi-asserted-by":"crossref","unstructured":"Farhadi, A., Hajiaghayi, M.T., Mai, T., Rao, A., Rossi, R.A.: Approximate maximum matching in random streams. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 1773\u20131785 (2020)","key":"10155_CR17","DOI":"10.1137\/1.9781611975994.108"},{"issue":"2\u20133","key":"10155_CR18","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theor. Comput. Sci. 348(2\u20133), 207\u2013216 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.013","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kale, S., Mitrovic, S., Svensson, O.: Weighted matchings via unweighted augmentations. In: P. Robinson, F. Ellen (eds.) Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29\u2013August 2, 2019, pp. 491\u2013500. ACM (2019)","key":"10155_CR19","DOI":"10.1145\/3293611.3331603"},{"unstructured":"Garg, P., Kale, S., Rohwedder, L., Svensson, O.: Robust algorithms under adversarial injections. In: A. Czumaj, A. Dawar, E. Merelli (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8\u201311, 2020, Saarbr\u00fccken, Germany (Virtual Conference), LIPIcs, vol. 168, pp. 56:1\u201356:15. Schloss Dagstuhl\u2013Leibniz Zentrum f\u00fcr Informatik (2020)","key":"10155_CR20"},{"unstructured":"Ghaffari, M., Wajc, D.: Simplified and space-optimal semi-streaming (2+epsilon)\u2013approximate matching. In: J.T. Fineman, M. Mitzenmacher (eds.) 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8\u20139, 2019\u2013San Diego, CA, USA, OASICS, vol. 69, pp. 13:1\u201313:8. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019)","key":"10155_CR21"},{"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, SODA\u201912, pp. 468\u2013485. SIAM (2012). http:\/\/dl.acm.org\/citation.cfm?id=2095116.2095157","key":"10155_CR22","DOI":"10.1137\/1.9781611973099.41"},{"doi-asserted-by":"crossref","unstructured":"Guruswami, V., Onak, K.: Superlinear lower bounds for multipass graph processing. In: Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5\u20137 June, 2013, pp. 287\u2013298 (2013)","key":"10155_CR23","DOI":"10.1109\/CCC.2013.37"},{"unstructured":"Kale, S., Tirodkar, S.: Maximum matching in two, three, and a few more passes over graph streams. In: K. Jansen, J.D.P. Rolim, D. Williamson, S.S. Vempala (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16\u201318, 2017, Berkeley, CA, USA (2017)","key":"10155_CR24"},{"doi-asserted-by":"publisher","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6\u20138, 2013, pp. 1679\u20131697 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.121","key":"10155_CR25","DOI":"10.1137\/1.9781611973105.121"},{"doi-asserted-by":"crossref","unstructured":"Kapralov, M.: Space lower bounds for approximating maximum matching in the edge arrival model. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 1874\u20131893. SIAM (2021)","key":"10155_CR26","DOI":"10.1137\/1.9781611976465.112"},{"doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Approximating matching size from random streams. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 734\u2013751 (2014)","key":"10155_CR27","DOI":"10.1137\/1.9781611973402.55"},{"doi-asserted-by":"crossref","unstructured":"Kapralov, M., Mitrovic, S., Norouzi-Fard, A., Tardos, J.: Space efficient approximation to maximum matching size from uniform edge samples. In: Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 1753\u20131772 (2020)","key":"10155_CR28","DOI":"10.1137\/1.9781611975994.107"},{"doi-asserted-by":"crossref","unstructured":"Konrad, C.: Maximum matching in turnstile streams. In: Algorithms\u2013ESA 2015\u201323rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings, pp.840\u2013852 (2015)","key":"10155_CR29","DOI":"10.1007\/978-3-662-48350-3_70"},{"unstructured":"Konrad, C.: A simple augmentation method for matchings with applications to streaming algorithms. In: I. Potapov, P.G. Spirakis, J. Worrell (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27\u201331, 2018, Liverpool, UK, LIPIcs, vol. 117, pp. 74:1\u201374:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)","key":"10155_CR30"},{"doi-asserted-by":"crossref","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15\u201317, 2012. Proceedings, pp. 231\u2013242 (2012)","key":"10155_CR31","DOI":"10.1007\/978-3-642-32512-0_20"},{"doi-asserted-by":"crossref","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22\u201324, 2005, pp. 170\u2013181 (2005)","key":"10155_CR32","DOI":"10.1007\/11538462_15"},{"unstructured":"McGregor, A., Vorotnikova, S.: Planar matching in streams revisited. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2016, September 7-9, 2016, Paris, France, pp. 17:1\u201317:12 (2016)","key":"10155_CR33"},{"unstructured":"McGregor, A., Vorotnikova, S.: A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs. In: 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7\u201310, 2018, New Orleans, LA, USA, pp. 14:1\u201314:4 (2018)","key":"10155_CR34"},{"doi-asserted-by":"crossref","unstructured":"Paz, A., Schwartzman, G.: A (2 + epsilon)-approximation for maximum weight matching in the semi-streaming model. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 2153\u20132161 (2017)","key":"10155_CR35","DOI":"10.1137\/1.9781611974782.140"},{"unstructured":"Wajc, D.: Negative association: definition, properties, and applications (2023). https:\/\/www.cs.cmu.edu\/~dwajc\/notes\/Negative%20Association.pdf","key":"10155_CR36"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10155-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10155-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10155-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:17:41Z","timestamp":1724447861000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10155-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10155"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10155-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"7 November 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}