{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T04:05:47Z","timestamp":1788581147031,"version":"build-2803163510"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council, UK","doi-asserted-by":"crossref","award":["EP\/S03353X\/1"],"award-info":[{"award-number":["EP\/S03353X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>\n            We present dynamic algorithms with\n            <jats:italic>polylogarithmic<\/jats:italic>\n            update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio\n            <jats:italic>strictly better than 2<\/jats:italic>\n            . Specifically, we obtain a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1+\\tfrac{1}{\\sqrt {2}}+\\epsilon \\approx 1.707+\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            approximation in bipartite graphs and a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1.973+\\epsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms\u2019 approximation and worst-case update time bounds both hold w.h.p.\u00a0against adaptive adversaries.\n          <\/jats:p>\n          <jats:p>Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS\u201921) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.<\/jats:p>","DOI":"10.1145\/3679009","type":"journal-article","created":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T12:01:10Z","timestamp":1721736070000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1612-0296","authenticated-orcid":false,"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6488-9990","authenticated-orcid":false,"given":"Peter","family":"Kiss","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8386-7168","authenticated-orcid":false,"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1896-2948","authenticated-orcid":false,"given":"David","family":"Wajc","sequence":"additional","affiliation":[{"name":"Technion Israel Institute of Technology, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"e_1_3_4_2_2","first-page":"477","volume-title":"Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud and S\u00f8ren Dahlgaard. 2016. Popular conjectures as a barrier for dynamic planar graph algorithms. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS). 477\u2013486."},{"key":"e_1_3_4_3_2","first-page":"434","volume-title":"Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS). 434\u2013443."},{"key":"e_1_3_4_4_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ic.2012.10.006","article-title":"Linear programming in the semi-streaming model with application to the maximum matching problem","volume":"222","author":"Ahn Kook Jin","year":"2013","unstructured":"Kook Jin Ahn and Sudipto Guha. 2013. Linear programming in the semi-streaming model with application to the maximum matching problem. Information and Computation 222 (2013), 59\u201379.","journal-title":"Information and Computation"},{"key":"e_1_3_4_5_2","first-page":"79:1\u201379:16","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Arar Moab","year":"2018","unstructured":"Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. 2018. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP). 79:1\u201379:16."},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/3564246.3585110","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)","author":"Assadi Sepehr","year":"2023","unstructured":"Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li. 2023. On regularity lemma and barriers in streaming and dynamic matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). 131\u2013144."},{"key":"e_1_3_4_7_2","first-page":"627","volume-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. 2022. Semi-streaming bipartite matching in fewer passes and optimal space. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 627\u2013669."},{"key":"e_1_3_4_8_2","unstructured":"Sepehr Assadi and Sanjeev Khanna. 2024. Improved bounds for fully dynamic matching via ordered ruzsa-szemer\u00e9di graphs. arXiv preprint arXiv:2406.13573 (2024)."},{"issue":"3","key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3355903","article-title":"The stochastic matching problem with (very) few queries","volume":"7","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, Sanjeev Khanna, and Yang Li. 2019. The stochastic matching problem with (very) few queries. ACM Transactions on Economics and Computation (TEAC) 7, 3 (2019), 1\u201319.","journal-title":"ACM Transactions on Economics and Computation (TEAC)"},{"key":"e_1_3_4_10_2","first-page":"1345","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Assadi Sepehr","year":"2016","unstructured":"Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. 2016. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1345\u20131364."},{"key":"e_1_3_4_11_2","volume-title":"Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Azarmehr Amir","year":"2024","unstructured":"Amir Azarmehr, Soheil Behnezhad, and Mohammad Roghani. 2024. Fully dynamic matching: \\((2-\\sqrt {2})\\) -Approximation in polylog update time. In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3040\u20133061."},{"issue":"1","key":"e_1_3_4_12_2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1137\/130914140","article-title":"Fully dynamic maximal matching in  \\({O}(\\log n)\\)  update time","volume":"44","author":"Baswana Surender","year":"2015","unstructured":"Surender Baswana, Manoj Gupta, and Sandeep Sen. 2015. Fully dynamic maximal matching in \\({O}(\\log n)\\) update time. SIAM Journal on Computing (SICOMP) 44, 1 (2015), 88\u2013113.","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"e_1_3_4_13_2","first-page":"873","volume-title":"Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS)","author":"Behnezhad Soheil","year":"2022","unstructured":"Soheil Behnezhad. 2022. Time-optimal sublinear algorithms for matching and vertex cover. In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 873\u2013884."},{"key":"e_1_3_4_14_2","first-page":"129","volume-title":"Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Behnezhad Soheil","year":"2023","unstructured":"Soheil Behnezhad. 2023. Dynamic algorithms for maximum matching size. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 129\u2013162."},{"key":"e_1_3_4_15_2","first-page":"382","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. 2019. Fully dynamic maximal independent set with polylogarithmic update time. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 382\u2013405."},{"key":"e_1_3_4_16_2","unstructured":"Soheil Behnezhad and Alma Ghafari. 2024. Fully dynamic matching and ordered ruzsa-szemer\u00e9di graphs. In Proceedings of the 65th Symposium on Foundations of Computer Science (FOCS). To appear."},{"key":"e_1_3_4_17_2","first-page":"3529","volume-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Behnezhad Soheil","year":"2022","unstructured":"Soheil Behnezhad and Sanjeev Khanna. 2022. New trade-offs for fully dynamic matching via hierarchical EDCS. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 3529\u20133566."},{"key":"e_1_3_4_18_2","first-page":"2492","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Behnezhad Soheil","year":"2020","unstructured":"Soheil Behnezhad, Jakub \u0141\u0105cki, and Vahab Mirrokni. 2020. Fully dynamic matching: Beating 2-approximation in \\({\\Delta }^{\\epsilon }\\) update time. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2492\u20132508."},{"key":"e_1_3_4_19_2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1145\/3564246.3585231","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)","author":"Behnezhad Soheil","year":"2023","unstructured":"Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. 2023. Sublinear time algorithms and complexity of approximate maximum matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). 267\u2013280."},{"key":"e_1_3_4_20_2","first-page":"1671","volume-title":"Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC)","author":"Beimel Amos","year":"2022","unstructured":"Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. 2022. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 1671\u20131684."},{"key":"e_1_3_4_21_2","volume-title":"Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Bernstein Aaron","year":"2021","unstructured":"Aaron Bernstein, Aditi Dudeja, and Zachary Langley. 2021. A framework for dynamic matching in weighted graphs. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC). 668\u2013681."},{"key":"e_1_3_4_22_2","doi-asserted-by":"crossref","first-page":"1899","DOI":"10.1137\/1.9781611975482.115","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bernstein Aaron","year":"2019","unstructured":"Aaron Bernstein, Sebastian Forster, and Monika Henzinger. 2019. A deamortization approach for dynamic spanner and dynamic maximal matching. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1899\u20131918."},{"key":"e_1_3_4_23_2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-662-47672-7_14","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP)","author":"Bernstein Aaron","year":"2015","unstructured":"Aaron Bernstein and Cliff Stein. 2015. Fully dynamic matching in bipartite graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP). 167\u2013179."},{"key":"e_1_3_4_24_2","first-page":"692","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bernstein Aaron","year":"2016","unstructured":"Aaron Bernstein and Cliff Stein. 2016. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 692\u2013711."},{"issue":"4","key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1007\/s00453-019-00630-4","article-title":"Deterministic dynamic matching in  \\({O}(1)\\)  update time","volume":"82","author":"Bhattacharya Sayan","year":"2020","unstructured":"Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. 2020. Deterministic dynamic matching in \\({O}(1)\\) update time. Algorithmica 82, 4 (2020), 1057\u20131080.","journal-title":"Algorithmica"},{"issue":"3","key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1137\/140998925","article-title":"Deterministic fully dynamic data structures for vertex cover and matching","volume":"47","author":"Bhattacharya Sayan","year":"2018","unstructured":"Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing (SICOMP) 47, 3 (2018), 859\u2013887.","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"e_1_3_4_27_2","first-page":"398","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bhattacharya Sayan","year":"2016","unstructured":"Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 2016. New deterministic approximation algorithms for fully dynamic matching. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC). 398\u2013411."},{"key":"e_1_3_4_28_2","first-page":"470","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bhattacharya Sayan","year":"2017","unstructured":"Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in \\({O} (\\log ^3 n)\\) worst case update time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 470\u2013489."},{"key":"e_1_3_4_29_2","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Bhattacharya Sayan","year":"2021","unstructured":"Sayan Bhattacharya and Peter Kiss. 2021. Deterministic rounding of dynamic fractional matchings. In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP). 27:1\u201327:14."},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1145\/3564246.3585252","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bhattacharya Sayan","year":"2023","unstructured":"Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. 2023. Sublinear algorithms for (1.5+ \\(\\epsilon\\) )-approximate matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). 254\u2013266."},{"key":"e_1_3_4_31_2","first-page":"1563","volume-title":"Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS)","author":"Bhattacharya Sayan","year":"2024","unstructured":"Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. 2024. Dynamic \\((1+\\epsilon)\\) -Approximate matching size in truly sublinear update time. In Proceedings of the 56th Symposium on Foundations of Computer Science (FOCS). 1563\u20131588."},{"key":"e_1_3_4_32_2","doi-asserted-by":"crossref","unstructured":"Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak and David Wajc. 2023. Dynamic matching with better-than-2 approximation in polylogarithmic update time. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM 100\u2013128.","DOI":"10.1137\/1.9781611977554.ch5"},{"key":"e_1_3_4_33_2","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC)","author":"Bhattacharya Sayan","year":"2024","unstructured":"Sayan Bhattacharya, Peter Kiss, Aaron Sidford, and David Wajc. 2024. Near-optimal dynamic rounding of fractional matchings in bipartite graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC). 59\u201370."},{"key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"1872","DOI":"10.1137\/1.9781611975482.113","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bhattacharya Sayan","year":"2019","unstructured":"Sayan Bhattacharya and Janardhan Kulkarni. 2019. Deterministically maintaining a \\((2+\\epsilon)\\) -approximate minimum vertex cover in \\({O}(1\/\\epsilon ^2)\\) amortized update time. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1872\u20131885."},{"key":"e_1_3_4_35_2","first-page":"456","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"Brand Jan van den","year":"2019","unstructured":"Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. 2019. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 456\u2013480."},{"key":"e_1_3_4_36_2","first-page":"33:1\u201333:14","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Charikar Moses","year":"2018","unstructured":"Moses Charikar and Shay Solomon. 2018. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP). 33:1\u201333:14."},{"key":"e_1_3_4_37_2","first-page":"370","volume-title":"Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS)","author":"Chechik Shiri","year":"2019","unstructured":"Shiri Chechik and Tianyi Zhang. 2019. Fully dynamic maximal independent set in expected poly-log update time. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 370\u2013381."},{"key":"e_1_3_4_38_2","unstructured":"Jiale Chen Aaron Sidford and Ta-Wei Tu. 2023. Entropy regularization and faster decremental matching in general graphs. arXiv preprint arXiv:2312.09077 (2023)."},{"key":"e_1_3_4_39_2","first-page":"389","volume-title":"Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC)","author":"Chuzhoy Julia","year":"2019","unstructured":"Julia Chuzhoy and Sanjeev Khanna. 2019. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC). 389\u2013400."},{"key":"e_1_3_4_40_2","first-page":"96","volume-title":"Proceedings of the 17th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Crouch Michael","year":"2014","unstructured":"Michael Crouch and Daniel M. Stubbs. 2014. Improved streaming algorithms for weighted matching, via unweighted matching. In Proceedings of the 17th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 96."},{"key":"e_1_3_4_41_2","first-page":"48:1\u201348:14","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"Dahlgaard S\u00f8ren","year":"2016","unstructured":"S\u00f8ren Dahlgaard. 2016. On the hardness of partially dynamic graph problems and connections to diameter. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP). 48:1\u201348:14."},{"issue":"1","key":"e_1_3_4_42_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2529989","article-title":"Linear-time approximation for maximum weight matching","volume":"61","author":"Duan Ran","year":"2014","unstructured":"Ran Duan and Seth Pettie. 2014. Linear-time approximation for maximum weight matching. Journal of the ACM (JACM) 61, 1 (2014), 1.","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"e_1_3_4_43_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","article-title":"Balls and bins: A study in negative dependence","volume":"13","author":"Dubhashi Devdatt P.","year":"1998","unstructured":"Devdatt P. Dubhashi and Desh Ranjan. 1998. Balls and bins: A study in negative dependence. Random Struct. Algorithms 13, 2 (1998), 99\u2013124.","journal-title":"Random Struct. Algorithms"},{"key":"e_1_3_4_44_2","unstructured":"Aditi Dudeja. 2024. A note on rounding matchings in general graphs. arXiv preprint arXiv:2402.03068 (2024)."},{"issue":"125","key":"e_1_3_4_45_2","first-page":"55","article-title":"Maximum matching and a polyhedron with 0, 1-vertices","volume":"69","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds. 1965. Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards B 69, 125-130 (1965), 55\u201356.","journal-title":"Journal of Research of the National Bureau of Standards B"},{"issue":"3","key":"e_1_3_4_46_2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17, 3 (1965), 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"key":"e_1_3_4_47_2","first-page":"492","volume-title":"Proceedings of the 16th Annual European Symposium on Algorithms (ESA)","author":"Eggert Sebastian","year":"2009","unstructured":"Sebastian Eggert, Lasse Kliemann, and Anand Srivastav. 2009. Bipartite graph matchings in the semi-streaming model. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA). 492\u2013503."},{"key":"e_1_3_4_48_2","first-page":"389","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Epstein Leah","year":"2013","unstructured":"Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. 2013. Improved bounds for online preemptive matching. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS). 389."},{"key":"e_1_3_4_49_2","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1109\/ICDMW.2016.0092","volume-title":"2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW)","author":"Esfandiari Hossein","year":"2016","unstructured":"Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh. 2016. Finding large matchings in semi-streaming. In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW). 608\u2013614."},{"key":"e_1_3_4_50_2","first-page":"101","volume-title":"Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS)","author":"Fahrbach Matthew","year":"2018","unstructured":"Matthew Fahrbach, Gary L. Miller, Richard Peng, Saurabh Sawlani, Junxing Wang, and Shen Chen Xu. 2018. Graph sketching against adaptive adversaries applied to the minimum degree algorithm. In Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS). 101\u2013112."},{"issue":"2","key":"e_1_3_4_51_2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","article-title":"On graph problems in a semi-streaming model","volume":"348","author":"Feigenbaum Joan","year":"2005","unstructured":"Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2005. On graph problems in a semi-streaming model. Theoretical Computer Science (TCS) 348, 2-3 (2005), 207\u2013216.","journal-title":"Theoretical Computer Science (TCS)"},{"key":"e_1_3_4_52_2","volume-title":"Proceedings of the 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Feldman Moran","year":"2022","unstructured":"Moran Feldman and Ariel Szarf. 2022. Maximum matching sans maximal matching: A new approach for finding maximum matchings in the data stream model. In Proceedings of the 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 33:1\u201333:24."},{"key":"e_1_3_4_53_2","first-page":"248","volume-title":"Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC)","author":"Fischer Manuela","year":"2022","unstructured":"Manuela Fischer, Slobodan Mitrovi\u0107, and Jara Uitto. 2022. Deterministic \\((1+ \\epsilon)\\) -approximate maximum matching with poly \\((1\/\\epsilon)\\) passes in the semi-streaming model and beyond. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 248\u2013260."},{"key":"e_1_3_4_54_2","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA)","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and David Wajc. 2019. Simplified and space-optimal semi-streaming \\((2+ \\epsilon)\\) -approximate matching. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA). 13:1\u201313:8."},{"key":"e_1_3_4_55_2","first-page":"468","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Goel Ashish","year":"2012","unstructured":"Ashish Goel, Michael Kapralov, and Sanjeev Khanna. 2012. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 468\u2013485."},{"issue":"3","key":"e_1_3_4_56_2","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1137\/100812513","article-title":"Perfect matchings in  \\({O}(n \\log n)\\)  time in regular bipartite graphs","volume":"42","author":"Goel Ashish","year":"2013","unstructured":"Ashish Goel, Michael Kapralov, and Sanjeev Khanna. 2013. Perfect matchings in \\({O}(n \\log n)\\) time in regular bipartite graphs. SIAM Journal on Computing (SICOMP) 42, 3 (2013), 1392\u20131404.","journal-title":"SIAM Journal on Computing (SICOMP)"},{"key":"e_1_3_4_57_2","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1137\/1.9781611977066.2","article-title":"Maintaining an EDCS in general graphs: Simpler, density-sensitive and with worst-case time bounds","author":"Grandoni Fabrizio","year":"2022","unstructured":"Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. 2022. Maintaining an EDCS in general graphs: Simpler, density-sensitive and with worst-case time bounds. Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA) (2022), 12\u201323.","journal-title":"Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA)"},{"key":"e_1_3_4_58_2","first-page":"548","volume-title":"Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS)","author":"Gupta Manoj","year":"2013","unstructured":"Manoj Gupta and Richard Peng. 2013. Fully dynamic \\((1+\\epsilon)\\) -approximate matchings. In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS). 548\u2013557."},{"key":"e_1_3_4_59_2","first-page":"21","volume-title":"Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC)","author":"Henzinger Monika","year":"2015","unstructured":"Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC). 21\u201330."},{"key":"e_1_3_4_60_2","volume-title":"Proceedings of the 20th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Kale Sagar","year":"2017","unstructured":"Sagar Kale and Sumedh Tirodkar. 2017. Maximum matching in two, three, and a few more passes over graph streams. In Proceedings of the 20th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 15:1\u201315:21."},{"key":"e_1_3_4_61_2","first-page":"1679","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kapralov Michael","year":"2013","unstructured":"Michael Kapralov. 2013. Better bounds for matchings in the streaming model. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1679\u20131697."},{"key":"e_1_3_4_62_2","first-page":"1874","volume-title":"Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kapralov Michael","year":"2021","unstructured":"Michael Kapralov. 2021. Space lower bounds for approximating maximum matching in the edge arrival model. In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1874\u20131893."},{"key":"e_1_3_4_63_2","first-page":"94:1\u201394:21","article-title":"Improving update times of dynamic matching algorithms from amortized to worst case","author":"Kiss Peter","year":"2022","unstructured":"Peter Kiss. 2022. Improving update times of dynamic matching algorithms from amortized to worst case. Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS) (2022), 94:1\u201394:21.","journal-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)"},{"key":"e_1_3_4_64_2","volume-title":"Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"Konrad Christian","year":"2018","unstructured":"Christian Konrad. 2018. A simple augmentation method for matchings with applications to streaming algorithms. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS). 74:1\u201374:16."},{"key":"e_1_3_4_65_2","first-page":"231","volume-title":"Proceedings of the 15th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Konrad Christian","year":"2012","unstructured":"Christian Konrad, Fr\u00e9d\u00e9ric Magniez, and Claire Mathieu. 2012. Maximum matching in semi-streaming with few passes. In Proceedings of the 15th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 231\u2013242."},{"key":"e_1_3_4_66_2","first-page":"19:1\u201319:18","volume-title":"Proceedings of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Konrad Christian","year":"2021","unstructured":"Christian Konrad and Kheeran K. Naidu. 2021. On two-pass streaming algorithms for maximum bipartite matching. In Proceedings of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 19:1\u201319:18."},{"key":"e_1_3_4_67_2","first-page":"1272","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Kopelowitz Tsvi","year":"2016","unstructured":"Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2016. Higher lower bounds from the 3SUM conjecture. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1272\u20131287."},{"issue":"1","key":"e_1_3_4_68_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn Harold W.","year":"1955","unstructured":"Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1-2 (1955), 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"key":"e_1_3_4_69_2","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Le Hung","year":"2022","unstructured":"Hung Le, Lazar Milenkovi\u0107, Shay Solomon, and Virginia Vassilevska Williams. 2022. Dynamic matching algorithms under vertex updates. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). 96:1\u201396:24."},{"key":"e_1_3_4_70_2","unstructured":"Yang P. Liu. 2024. On approximate fully-dynamic matching and online matrix-vector multiplication. In Proceedings of the 65th Symposium on Foundations of Computer Science (FOCS). To appear."},{"key":"e_1_3_4_71_2","first-page":"170","volume-title":"Proceedings of the 8th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"McGregor Andrew","year":"2005","unstructured":"Andrew McGregor. 2005. Finding graph matchings in data streams. In Proceedings of the 8th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 170\u2013181."},{"key":"e_1_3_4_72_2","first-page":"1122","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC)","author":"Nanongkai Danupon","year":"2017","unstructured":"Danupon Nanongkai and Thatchaphol Saranurak. 2017. Dynamic spanning forest with worst-case update time: Adaptive, Las Vegas, and \\({O} (n^{1\/2-\\varepsilon })\\) -time. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC). 1122\u20131129."},{"key":"e_1_3_4_73_2","first-page":"327","volume-title":"Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS)","author":"Nguyen Huy N.","year":"2008","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS). 327\u2013336."},{"key":"e_1_3_4_74_2","first-page":"1123","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Onak Krzysztof","year":"2012","unstructured":"Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1123\u20131131."},{"key":"e_1_3_4_75_2","first-page":"457","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC)","author":"Onak Krzysztof","year":"2010","unstructured":"Krzysztof Onak and Ronitt Rubinfeld. 2010. Maintaining a large matching and a small vertex cover. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). 457\u2013464."},{"issue":"1","key":"e_1_3_4_76_2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","article-title":"Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms","volume":"381","author":"Parnas Michal","year":"2007","unstructured":"Michal Parnas and Dana Ron. 2007. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science (TCS) 381, 1-3 (2007), 183\u2013196.","journal-title":"Theoretical Computer Science (TCS)"},{"issue":"2","key":"e_1_3_4_77_2","first-page":"18","article-title":"A  \\((2+\\epsilon)\\) -approximation for maximum weight matching in the semi-streaming model","volume":"15","author":"Paz Ami","year":"2018","unstructured":"Ami Paz and Gregory Schwartzman. 2018. A \\((2+\\epsilon)\\) -approximation for maximum weight matching in the semi-streaming model. ACM Transactions on Algorithms (TALG) 15, 2 (2018), 18.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_4_78_2","first-page":"712","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Peleg David","year":"2016","unstructured":"David Peleg and Shay Solomon. 2016. Dynamic \\((1+ \\epsilon)\\) -approximate matchings: A density-sensitive approach. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 712\u2013729."},{"key":"e_1_3_4_79_2","first-page":"111:1\u2013111:23","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Roghani Mohammad","year":"2022","unstructured":"Mohammad Roghani, Amin Saberi, and David Wajc. 2022. Beating the folklore algorithm for dynamic matching. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). 111:1\u2013111:23."},{"key":"e_1_3_4_80_2","first-page":"118","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sankowski Piotr","year":"2007","unstructured":"Piotr Sankowski. 2007. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 118\u2013126."},{"key":"e_1_3_4_81_2","first-page":"325","volume-title":"Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS)","author":"Solomon Shay","year":"2016","unstructured":"Shay Solomon. 2016. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS). 325\u2013334."},{"key":"e_1_3_4_82_2","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing Vadim G.","year":"1964","unstructured":"Vadim G. Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret Analiz 3 (1964), 25\u201330.","journal-title":"Diskret Analiz"},{"key":"e_1_3_4_83_2","first-page":"194","volume-title":"Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC)","author":"Wajc David","year":"2020","unstructured":"David Wajc. 2020. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 194\u2013207."},{"issue":"4","key":"e_1_3_4_84_2","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1137\/110828691","article-title":"Improved constant-time approximation algorithms for maximum matchings and other optimization problems","volume":"41","author":"Yoshida Yuichi","year":"2012","unstructured":"Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. 2012. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM Journal on Computing (SICOMP) 41, 4 (2012), 1074\u20131093.","journal-title":"SIAM Journal on Computing (SICOMP)"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3679009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3679009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:14Z","timestamp":1750294694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3679009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":83,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3679009"],"URL":"https:\/\/doi.org\/10.1145\/3679009","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2023-08-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}