{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328679,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:00:00Z","timestamp":1701129600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:00:00Z","timestamp":1701129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1357\/16","1357\/16"],"award-info":[{"award-number":["1357\/16","1357\/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":[[2024,4]]},"DOI":"10.1007\/s00453-023-01190-4","type":"journal-article","created":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T08:02:18Z","timestamp":1701158538000},"page":"1173-1209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Szarf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,28]]},"reference":[{"key":"1190_CR1","doi-asserted-by":"publisher","unstructured":"Konrad, C., Naidu, K.K.: On two-pass streaming algorithms for maximum bipartite matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2021, August 16\u201318, 2021. LIPIcs, vol. 207 (2021), pp. 19:1\u201319:18. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2021.19","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.19"},{"issue":"2","key":"1190_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/net.3230210203","volume":"21","author":"ML Balinski","year":"1991","unstructured":"Balinski, M.L., Gonzalez, J.: Maximum matchings in bipartite graphs via strong spanning trees. Networks 21(2), 165\u2013179 (1991). https:\/\/doi.org\/10.1002\/net.3230210203","journal-title":"Networks"},{"issue":"125\u2013130","key":"1190_CR3","first-page":"55","volume":"69","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bureau Stand. B 69(125\u2013130), 55\u201356 (1965)","journal-title":"J. Res. Natl. Bureau Stand. B"},{"issue":"4","key":"1190_CR4","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/0202019","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"1190_CR5","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."},{"key":"1190_CR6","doi-asserted-by":"publisher","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, January 10\u201313, 2021 (2021), pp. 1874\u20131893. https:\/\/doi.org\/10.1137\/1.9781611976465.112","DOI":"10.1137\/1.9781611976465.112"},{"key":"1190_CR7","doi-asserted-by":"publisher","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) (2012), pp. 468\u2013485. https:\/\/doi.org\/10.1137\/1.9781611973099.41","DOI":"10.1137\/1.9781611973099.41"},{"key":"1190_CR8","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), pp. 1679\u20131697. https:\/\/doi.org\/10.1137\/1.9781611973105.121","DOI":"10.1137\/1.9781611973105.121"},{"key":"1190_CR9","doi-asserted-by":"publisher","unstructured":"Konrad, C.: A simple augmentation method for matchings with applications to streaming algorithms. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS). LIPIcs, vol. 117 (2018), pp. 74:1\u201374:16. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.74","DOI":"10.4230\/LIPIcs.MFCS.2018.74"},{"key":"1190_CR10","doi-asserted-by":"publisher","unstructured":"Kale, S., Tirodkar, S.: Maximum matching in two, three, and a few more passes over graph streams. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA. LIPIcs, vol.\u00a081 (2017), pp. 15:1\u201315:21. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2017.15","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2017.15"},{"key":"1190_CR11","doi-asserted-by":"publisher","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum matching in semi-streaming with few passes. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques\u201415th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15\u201317, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7408, pp. 231\u2013242 (2012). https:\/\/doi.org\/10.1007\/978-3-642-32512-0_20","DOI":"10.1007\/978-3-642-32512-0_20"},{"key":"1190_CR12","doi-asserted-by":"publisher","unstructured":"Esfandiari, H., Hajiaghayi, M., Monemizadeh, M.: Finding large matchings in semi-streaming. In: Domeniconi, C., Gullo, F., Bonchi, F., Domingo-Ferrer, J., Baeza-Yates, R., Zhou, Z., Wu, X. (eds.) IEEE International Conference on Data Mining Workshops, ICDM Workshops 2016, December 12\u201315, 2016, Barcelona, Spain, pp. 608\u2013614. IEEE Computer Society (2016). https:\/\/doi.org\/10.1109\/ICDMW.2016.0092","DOI":"10.1109\/ICDMW.2016.0092"},{"key":"1190_CR13","doi-asserted-by":"publisher","unstructured":"Assadi, S.: A two-pass (conditional) lower bound for semi-streaming maximum matching. In: Naor, J.S., Buchbinder, N. (eds.) ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 708\u2013742. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.32","DOI":"10.1137\/1.9781611977073.32"},{"key":"1190_CR14","doi-asserted-by":"publisher","unstructured":"Azarmehr, A., Behnezhad, S., Roghani, M.: Fully dynamic matching: (2-$$\\surd $$2)-approximation in polylog update time. CoRR arXiv:abs\/2307.08772 (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.08772","DOI":"10.48550\/arXiv.2307.08772"},{"key":"1190_CR15","doi-asserted-by":"publisher","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), pp. 734\u2013751. https:\/\/doi.org\/10.1137\/1.9781611973402.55","DOI":"10.1137\/1.9781611973402.55"},{"key":"1190_CR16","doi-asserted-by":"publisher","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\u20136, 2017, Vienna, Austria. LIPIcs, vol.\u00a087, pp. 29:1\u201329:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.29","DOI":"10.4230\/LIPIcs.ESA.2017.29"},{"issue":"4","key":"1190_CR17","doi-asserted-by":"publisher","first-page":"48:1","DOI":"10.1145\/3230819","volume":"14","author":"H Esfandiari","year":"2018","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-48:23 (2018). https:\/\/doi.org\/10.1145\/3230819","journal-title":"ACM Trans. Algorithms"},{"key":"1190_CR18","doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S.: Planar matching in streams revisited. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), pp. 17:1\u201317:12 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.17","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.17"},{"key":"1190_CR19","doi-asserted-by":"publisher","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). OASICS, vol.\u00a061, pp. 14:1\u201314:4 (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.14","DOI":"10.4230\/OASIcs.SOSA.2018.14"},{"key":"1190_CR20","doi-asserted-by":"publisher","unstructured":"Assadi, S., Khanna, S., Li, Y.: On estimating maximum matching size in graph streams. In: Klein, P.N. (ed) 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. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.113","DOI":"10.1137\/1.9781611974782.113"},{"key":"1190_CR21","doi-asserted-by":"publisher","unstructured":"Assadi, S., Kol, G., Saxena, R.R., Yu, H.: Multi-pass graph streaming lower bounds for cycle counting, max-cut, matching size, and other problems. In: Irani, S. (ed) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 354\u2013364. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00041","DOI":"10.1109\/FOCS46700.2020.00041"},{"key":"1190_CR22","doi-asserted-by":"publisher","unstructured":"Assadi, S., N, V.: Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, June 21\u201325, 2021, pp. 612\u2013625. ACM (2021). https:\/\/doi.org\/10.1145\/3406325.3451110","DOI":"10.1145\/3406325.3451110"},{"key":"1190_CR23","doi-asserted-by":"publisher","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), pp. 1326\u20131344. https:\/\/doi.org\/10.1137\/1.9781611974331.ch92","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"1190_CR24","doi-asserted-by":"publisher","unstructured":"Assadi, S., Behnezhad, S., Khanna, S., Li, H.: On regularity lemma and barriers in streaming and dynamic matching. In: Saha, B., Servedio, R.A. (eds.) 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 131\u2013144. ACM (2023). https:\/\/doi.org\/10.1145\/3564246.3585110","DOI":"10.1145\/3564246.3585110"},{"key":"1190_CR25","doi-asserted-by":"publisher","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) and 9th International Workshop on Randomization and Computation (RANDOM) (2005), pp. 170\u2013181. https:\/\/doi.org\/10.1007\/11538462_15","DOI":"10.1007\/11538462_15"},{"issue":"4","key":"1190_CR26","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3154855","volume":"4","author":"KJ Ahn","year":"2018","unstructured":"Ahn, K.J., Guha, S.: Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Trans. Parallel Comput. 4(4), 17:1-17:40 (2018). https:\/\/doi.org\/10.1145\/3154855","journal-title":"ACM Trans. Parallel Comput."},{"key":"1190_CR27","unstructured":"Assadi, S., Jambulapati, A., Jin, Y., Sidford, A., Tian, K.: Semi-streaming bipartite matching in fewer passes and optimal space. arXiv e-prints pp. arXiv\u20132011 (2020)"},{"key":"1190_CR28","doi-asserted-by":"publisher","unstructured":"Assadi, S., Liu, S.C., Tarjan, R.E.: An auction algorithm for bipartite matching in streaming and massively parallel computation models. In: 4th Symposium on Simplicity in Algorithms (SOSA), pp. 165\u2013171 (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.18","DOI":"10.1137\/1.9781611976496.18"},{"key":"1190_CR29","doi-asserted-by":"publisher","unstructured":"Fischer, M., Mitrovic, S., Uitto, J.: Deterministic (1+$$\\epsilon $$)-approximate maximum matching with poly(1\/$$\\epsilon $$) passes in the semi-streaming model and beyond. In: Leonardi, S., Gupta, A. (eds.) STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20\u201324, 2022, pp. 248\u2013260. ACM (2022). https:\/\/doi.org\/10.1145\/3519935.3520039","DOI":"10.1145\/3519935.3520039"},{"key":"1190_CR30","doi-asserted-by":"publisher","unstructured":"Huang, S., Su, H.: $$(1-\\varepsilon )$$-approximate maximum weighted matching in poly$$(1\/\\varepsilon , \\log n)$$ time in the distributed and parallel settings. In: Oshman, R., Nolin, A., Halld\u00f3rsson, M.M., Balliu, A. (eds.), ACM Symposium on Principles of Distributed Computing (PODC), pp. 44\u201354. ACM (2023). https:\/\/doi.org\/10.1145\/3583668.3594570","DOI":"10.1145\/3583668.3594570"},{"key":"1190_CR31","doi-asserted-by":"publisher","unstructured":"Assadi, S.: A simple (1-$$\\epsilon $$)-approximation semi-streaming algorithm for maximum (weighted) matching. CoRR arXiv:abs\/2307.02968 (2023). https:\/\/doi.org\/10.48550\/arXiv.2307.02968","DOI":"10.48550\/arXiv.2307.02968"},{"key":"1190_CR32","doi-asserted-by":"publisher","unstructured":"Assadi, S., Behnezhad, S.: Beating two-thirds for random-order streaming matching. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021. LIPIcs, vol. 198, pp. 19:1\u201319:13 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.19","DOI":"10.4230\/LIPIcs.ICALP.2021.19"},{"key":"1190_CR33","doi-asserted-by":"publisher","unstructured":"Bernstein, A.: Improved bounds for matching in random-order streams. In: Czumaj, A. Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8\u201311, 2020, Saarbr\u00fccken, Germany. LIPIcs, vol. 168, (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020), pp. 12:1\u201312:13. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.12","DOI":"10.4230\/LIPIcs.ICALP.2020.12"},{"key":"1190_CR34","doi-asserted-by":"publisher","unstructured":"Crouch, M.S., Stubbs, D.M.: Improved streaming algorithms for weighted matching, via unweighted matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). LIPIcs, vol.\u00a028, pp. 96\u2013104 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.96","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2014.96"},{"issue":"3","key":"1190_CR35","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). https:\/\/doi.org\/10.1137\/100801901","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"1190_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-010-9438-5","volume":"62","author":"M Zelke","year":"2012","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. Algorithmica 62(1\u20132), 1\u201320 (2012). https:\/\/doi.org\/10.1007\/s00453-010-9438-5","journal-title":"Algorithmica"},{"issue":"2","key":"1190_CR37","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/3274668","volume":"15","author":"A Paz","year":"2019","unstructured":"Paz, A., Schwartzman, G.: A ($$2 + \\epsilon $$)-approximation for maximum weight matching in the semi-streaming model. ACM Trans. Algorithms 15(2), 18:1-18:15 (2019). https:\/\/doi.org\/10.1145\/3274668","journal-title":"ACM Trans. Algorithms"},{"key":"1190_CR38","doi-asserted-by":"publisher","unstructured":"Bernstein, A., Dudeja, A., Langley, Z.: A framework for dynamic matching in weighted graphs. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, June 21\u201325, 2021, pp. 668\u2013681. ACM (2021). https:\/\/doi.org\/10.1145\/3406325.3451113","DOI":"10.1145\/3406325.3451113"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01190-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01190-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01190-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T10:06:52Z","timestamp":1711620412000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01190-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,28]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["1190"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01190-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,11,28]]},"assertion":[{"value":"20 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The research leading to these results received funding from Israel Science Foundation (ISF) grants no. 1357\/16 and 459\/20. The authors have no other relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}