{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:56Z","timestamp":1781077676971,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Physical Sciences Research Council","award":["EP\\\/S03353X\\\/1"],"award-info":[{"award-number":["EP\\\/S03353X\\\/1"]}]},{"name":"Microsoft Research Faculty Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"NSF CAREER Award","award":["CCF-1844855"],"award-info":[{"award-number":["CCF-1844855"]}]},{"name":"NSF Grant","award":["CCF-1955039"],"award-info":[{"award-number":["CCF-1955039"]}]},{"name":"PayPal research award","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Sloan Research Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Taub Family Foundation ``Leader in Science and Technology' fellowship","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649648","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"59-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs"],"prefix":"10.1145","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":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2675-7610","authenticated-orcid":false,"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, Palo Alto, USA"}],"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, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_3_1","first-page":"1","article-title":"Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. In Proceedings of the 45th International Colloquium on Automata","volume":"79","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. 79:1\u201379:16.","journal-title":"Languages and Programming."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585110"},{"key":"e_1_3_2_1_5_1","first-page":"1","article-title":"Decremental Matching in General Graphs. In Proceedings of the 49th International Colloquium on Automata","volume":"11","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. 2022. Decremental Matching in General Graphs. In Proceedings of the 49th International Colloquium on Automata, Languages and Programming. 11:1\u201311:19.","journal-title":"Languages and Programming."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 35th Symposium on Discrete Algorithms.","author":"Azarmehr Amir","year":"2024","unstructured":"Amir Azarmehr, Soheil Behnezhad, and Mohammad Roghani. 2024. Fully Dynamic Matching: (2-\u221a 2)-Approximation in Polylog Update Time. In Proceedings of the 35th Symposium on Discrete Algorithms."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914140"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch6"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.140"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 31st Symposium on Discrete Algorithms. 2492\u20132508","author":"Behnezhad Soheil","year":"2020","unstructured":"Soheil Behnezhad, Jakub \u0141 \u0105cki, and Vahab Mirrokni. 2020. Fully Dynamic Matching: Beating 2-Approximation in \u0394 ^\u220a Update Time. In Proceedings of the 31st Symposium on Discrete Algorithms. 2492\u20132508."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520064"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.115"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00108"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00630-4"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.54"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 28th Symposium on Discrete Algorithms. 470\u2013489","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 ( olog^3 n) Worst Case Update Time. In Proceedings of the 28th Symposium on Discrete Algorithms. 470\u2013489."},{"key":"e_1_3_2_1_21_1","first-page":"1","article-title":"Deterministic Rounding of Dynamic Fractional Matchings. In Proceedings of the 48th International Colloquium on Automata","volume":"27","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. 27:1\u201327:14.","journal-title":"Languages and Programming."},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 64th Symposium on Foundations of Computer Science, 1563\u20131588","author":"Bhattacharya Sayan","year":"2023","unstructured":"Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. 2023. Dynamic (1+\u220a )-Approximate Matching Size in Truly Sublinear Update Time. Proceedings of the 64th Symposium on Foundations of Computer Science, 1563\u20131588."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Sayan Bhattacharya Peter Kiss Aaron Sidford and David Wajc. 2024. Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. arxiv:2306.11828.","DOI":"10.1145\/3618260.3649648"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 30th Symposium on Discrete Algorithms. 1872\u20131885","author":"Bhattacharya Sayan","year":"2019","unstructured":"Sayan Bhattacharya and Janardhan Kulkarni. 2019. Deterministically Maintaining a (2+\u220a )-Approximate Minimum Vertex Cover in O(1\/^2) Amortized Update Time. In Proceedings of the 30th Symposium on Discrete Algorithms. 1872\u20131885."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 31st European Symposium on Algorithms. 22:1\u201322:19","author":"Blikstad Joakim","year":"2023","unstructured":"Joakim Blikstad and Peter Kiss. 2023. Incremental (1-\u220a )-approximate dynamic matching in O((1\/\u220a )) update time. In Proceedings of the 31st European Symposium on Algorithms. 22:1\u201322:19."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00036"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_23"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0205-0"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds. In Proceedings of the 45th International Colloquium on Automata","volume":"33","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. 33:1\u201333:14.","journal-title":"Languages and Programming."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316320"},{"key":"e_1_3_2_1_35_1","first-page":"1","article-title":"On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. In Proceedings of the 43rd International Colloquium on Automata","volume":"48","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. 48:1\u201348:14.","journal-title":"Languages and Programming."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 30th Symposium on Discrete Algorithms. 1886\u20131898","author":"Grandoni Fabrizio","year":"2019","unstructured":"Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. 2019. (1+\u220a )-Approximate Incremental Matching in Constant Deterministic Amortized Time. In Proceedings of the 30th Symposium on Discrete Algorithms. 1886\u20131898."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.2"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_41_1","volume-title":"Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS). 29","author":"Gupta Manoj","year":"2014","unstructured":"Manoj Gupta, Venkatesh Raman, and SP Suresh. 2014. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS). 29, 227\u2013239."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/647674.731515"},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the 49th International Colloquium on Automata, Languages and Programming.","author":"Jambulapati Arun","year":"2022","unstructured":"Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. 2022. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In Proceedings of the 49th International Colloquium on Automata, Languages and Programming."},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science, 94:1\u201394:21","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, 94:1\u201394:21."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 49th Symposium on Theory of Computing. 1122\u20131129","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-\u03b5 )-time. In Proceedings of the 49th Symposium on Theory of Computing. 1122\u20131129."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_49_1","volume-title":"Proceedings of the 27th Symposium on Discrete Algorithms. 712\u2013729","author":"Peleg David","year":"2016","unstructured":"David Peleg and Shay Solomon. 2016. Dynamic (1+ \u220a )-approximate matchings: a density-sensitive approach. In Proceedings of the 27th Symposium on Discrete Algorithms. 712\u2013729."},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science. 111:1\u2013111:23","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. 111:1\u2013111:23."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.028"},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of the 12th Innovations in Theoretical Computer Science. 57:1\u201357:20","author":"Solomon Noam","year":"2021","unstructured":"Noam Solomon and Shay Solomon. 2021. A Generalized Matching Reconfiguration Problem. In Proceedings of the 12th Innovations in Theoretical Computer Science. 57:1\u201357:20."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14031-0_53"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384258"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599458"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32726-1_32"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649648","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649648","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649648"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":57,"alternative-id":["10.1145\/3618260.3649648","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649648","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}