{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:42Z","timestamp":1773704802775,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594570","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"44-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["(1-\n            <i>\u03f5<\/i>\n            )-Approximate Maximum Weighted Matching in poly(1\/\n            <i>\u03f5<\/i>\n            , log\n            <i>n<\/i>\n            ) Time in the Distributed and Parallel Settings"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9799-0981","authenticated-orcid":false,"given":"Shang-En","family":"Huang","sequence":"first","affiliation":[{"name":"Boston College, Chestnut Hill, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7970-9604","authenticated-orcid":false,"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"Boston College, Chestnut Hill, MA, United States"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proc. 32nd International Symposium on Distributed Computing (DISC). 6:1--6:17","author":"Ahmadi Mohamad","year":"2018","unstructured":"Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. 2018. Distributed Approximate Maximum Matching in the CONGEST Model. In Proc. 32nd International Symposium on Distributed Computing (DISC). 6:1--6:17."},{"key":"e_1_3_2_1_2_1","volume-title":"Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model. CoRR abs\/1104.4058","author":"Ahn Kook Jin","year":"2011","unstructured":"Kook Jin Ahn and Sudipto Guha. 2011. Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model. CoRR abs\/1104.4058 (2011). arXiv:1104.4058 http:\/\/arxiv.org\/abs\/1104.4058"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087806"},{"key":"e_1_3_2_1_6_1","unstructured":"Aaron Bernstein and Aditi Dudeja. 2023. Private Communication."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646244.681623"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538423"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00393-9"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings 42nd ACM Symposium on Theory of Computing. 465--474","author":"Duan R.","unstructured":"R. Duan and S. Pettie. 2010. Connectivity Oracles for Failure Prone Graphs. In Proceedings 42nd ACM Symposium on Theory of Computing. 465--474."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_3_2_1_12_1","volume-title":"Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B","author":"Edmonds J.","year":"1965","unstructured":"J. Edmonds. 1965. Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125--130."},{"key":"e_1_3_2_1_13_1","volume-title":"Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs","volume":"20","author":"Faour Salwa","year":"2021","unstructured":"Salwa Faour, Marc Fuchs, and Fabian Kuhn. 2021. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. In 25th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 217). 17:1--17:20."},{"key":"e_1_3_2_1_14_1","volume-title":"Improved deterministic distributed matching via rounding. Distributed Computing","author":"Fischer Manuela","year":"2018","unstructured":"Manuela Fischer. 2018. Improved deterministic distributed matching via rounding. Distributed Computing (2018), 1--13."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520039"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1009"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.65"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_3_2_1_24_1","unstructured":"S. Hanke and S. Hougardy. 2010. New Approximation Algorithms for the Weighted Matching Problem. Research Report No. 101010. Research Institute for Discrete Mathematics University of Bonn."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00048"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.03.005"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2212.14425"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714403"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings 21st IEEE Symposium on Foundations of Computer Science (FOCS). 17--27","author":"Micali S.","unstructured":"S. Micali and V. V. Vazirani. 1980. An [EQUATION] algorithm for finding maximum matching in general graphs. In Proceedings 21st IEEE Symposium on Foundations of Computer Science (FOCS). 17--27."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400863.1400880"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305952"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30186-8_24"}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","location":"Orlando FL USA","acronym":"PODC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594570","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:54Z","timestamp":1750178274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594570"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":38,"alternative-id":["10.1145\/3583668.3594570","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594570","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}