{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:24Z","timestamp":1750220184267,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["ME 3619\/3-2 and ME 3619\/4-1"],"award-info":[{"award-number":["ME 3619\/3-2 and ME 3619\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Matching is a popular combinatorial optimization problem with numerous applications in both commercial and scientific fields. Computing optimal matchings w.r.t. cardinality or weight can be done in polynomial time; still, this task can become infeasible for very large networks. Thus, several approximation algorithms that trade solution quality for a faster running time have been proposed. For networks that change over time, fully dynamic algorithms that efficiently maintain an approximation of the optimal matching after a graph update have been introduced as well. However, no semi- or fully dynamic algorithm for (approximate) maximum weighted matching has been implemented.<\/jats:p>\n          <jats:p>\n            In this article, we focus on the problem of maintaining a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 1\/2 \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximation of a maximum weighted matching (MWM) in fully dynamic graphs. Limitations of existing algorithms for this problem are (i) high constant factors in their time complexity, (ii) the fact that none of them supports batch updates, and (iii) the lack of a practical implementation, meaning that their actual performance on real-world graphs has not been investigated. We propose and implement a new batch-dynamic\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 1\/2 \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximation algorithm for MWM based on the Suitor algorithm and its local edge domination strategy [Manne and Halappanavar, IPDPS 2014]. We provide a detailed analysis of our algorithm and prove its approximation guarantee. Despite having a worst-case running time of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathcal {O}(n + m) \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for a single graph update, our extensive experimental evaluation shows that our algorithm is much faster in practice. For example, compared to a static recomputation with sequential\n            <jats:sans-serif>Suitor<\/jats:sans-serif>\n            , single-edge updates are handled up to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 10^5\\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 10^6\\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            faster, while batches of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 10^4 \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            edge updates are handled up to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 10^2\\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( 10^3\\times \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            faster.\n          <\/jats:p>","DOI":"10.1145\/3529228","type":"journal-article","created":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:05:12Z","timestamp":1657195512000},"page":"1-41","source":"Crossref","is-referenced-by-count":2,"title":["A Batch-dynamic Suitor Algorithm\u00a0for Approximating Maximum Weighted Matching"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3160-1509","authenticated-orcid":false,"given":"Eugenio","family":"Angriman","sequence":"first","affiliation":[{"name":"Department of Computer Science, Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1695-4880","authenticated-orcid":false,"given":"Micha\u0142","family":"Boro\u0144","sequence":"additional","affiliation":[{"name":"Visiting scholar at Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7769-726X","authenticated-orcid":false,"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,7,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2012.257"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12070127"},{"key":"e_1_3_3_4_2","first-page":"7:1\u20137:16","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","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\u201918). 7:1\u20137:16."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130404"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338529"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106158"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/140998925"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897568"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_66"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198788348.001.0001"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_3_3_15_2","unstructured":"Moses Charikar and Shay Solomon. 2017. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. Retrieved from http:\/\/arxiv.org\/abs\/1711.06883."},{"key":"e_1_3_3_16_2","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201914)","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 Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201914). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44867-5_9"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.12"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3155301"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/100801901"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum Sampath Kannan Andrew McGregor Siddharth Suri and Jian Zhang. 2005. On graph problems in a semi-streaming model. Theor. Comput. Sci. 348 2\u20133 (2005) 207\u2013216.","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320229"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6502"},{"key":"e_1_3_3_26_2","volume-title":"Proceedings of the Symposium on Simplicity in Algorithms","volume":"69","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and David Wajc. 2019. Simplified and space-optimal semi-streaming \\( (2 + \\varepsilon) \\) -approximate matching. In Proceedings of the Symposium on Simplicity in Algorithms, Vol. 69."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0505-z"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.114"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.58"},{"key":"e_1_3_3_31_2","unstructured":"Jaap-Henk Hoepman. 2004. Simple distributed weighted matchings. Retrieved from http:\/\/arxiv.org\/abs\/cs.DC\/0410047."},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/3-540-57899-4_44","volume-title":"Proceedings of the 19th International Workshop Graph-Theoretic Concepts in Computer Science (LNCS)","volume":"790","author":"Ivkovi\u0107 Zoran","year":"1993","unstructured":"Zoran Ivkovi\u0107 and Errol L. Lloyd. 1993. Fully dynamic maintenance of vertex cover. In Proceedings of the 19th International Workshop Graph-Theoretic Concepts in Computer Science (LNCS), Vol. 790. Springer, 99\u2013111."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105982"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1026304"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.53"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_3_38_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler Eugene L.","year":"2001","unstructured":"Eugene L. Lawler. 2001. Combinatorial Optimization: Networks and Matroids. Courier Corporation."},{"key":"e_1_3_3_39_2","volume-title":"Matching Theory","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2009","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Michael D. Plummer. 2009. Matching Theory. Vol. 367. American Mathematical Soc."},{"key":"e_1_3_3_40_2","first-page":"708","volume-title":"Proceedings of the International Conference on Parallel Processing and Applied Mathematics","author":"Manne Fredrik","year":"2007","unstructured":"Fredrik Manne and Rob H. Bisseling. 2007. A parallel approximation algorithm for the weighted maximum matching problem. In Proceedings of the International Conference on Parallel Processing and Applied Mathematics. Springer, 708\u2013717."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.61"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_19"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.12"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1187-5"},{"key":"e_1_3_3_47_2","first-page":"45","article-title":"Introducing the graph 500","volume":"19","author":"Murphy Richard C.","year":"2010","unstructured":"Richard C. Murphy, Kyle B. Wheeler, Brian W. Barrett, and James A. Ang. 2010. Introducing the graph 500. Cray Users Group 19 (2010), 45\u201374.","journal-title":"Cray Users Group"},{"issue":"1","key":"e_1_3_3_48_2","first-page":"1","article-title":"Simple deterministic algorithms for fully dynamic maximal matching","volume":"12","author":"Neiman Ofer","year":"2015","unstructured":"Ofer Neiman and Shay Solomon. 2015. Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algor. 12, 1 (2015), 1\u201315.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_3_50_2","article-title":"Planet dump. Retrieved from https:\/\/planet.osm.org","author":"contributors OpenStreetMap","year":"2017","unstructured":"OpenStreetMap contributors. 2017. Planet dump. Retrieved from https:\/\/planet.osm.org; https:\/\/www.openstreetmap.org.","journal-title":"https:\/\/www.openstreetmap.org"},{"key":"e_1_3_3_51_2","first-page":"2153","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Paz Ami","year":"2017","unstructured":"Ami Paz and Gregory Schwartzman. 2017. A \\( (2+\\varepsilon) \\) -approximation for maximum weight matching in the semi-streaming model. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2153\u20132161."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.005"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_24"},{"key":"e_1_3_3_54_2","first-page":"118","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Sankowski Piotr","year":"2007","unstructured":"Piotr Sankowski. 2007. Faster dynamic matchings and vertex connectivity. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 118\u2013126."},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.028"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.58"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761644"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3529228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:20Z","timestamp":1750186940000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3529228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":58,"alternative-id":["10.1145\/3529228"],"URL":"https:\/\/doi.org\/10.1145\/3529228","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2022,7,7]]}}}