{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:21:43Z","timestamp":1777965703319,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["335288-OptApprox"],"award-info":[{"award-number":["335288-OptApprox"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","award":["P2ELP2_181772"],"award-info":[{"award-number":["P2ELP2_181772"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331603","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"491-500","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Weighted Matchings via Unweighted Augmentations"],"prefix":"10.1145","author":[{"given":"Buddhima","family":"Gamlath","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagar","family":"Kale","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Slobodan","family":"Mitrovic","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154855"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310533"},{"key":"e_1_3_2_1_7_1","unstructured":"Sepehr Assadi Xiaorui Sun and Omri Weinstein. 2018. Massively parallel algo-rithms for finding well-connected components in sparse graphs.arXiv preprintar Xiv:1805.02974(2018).  Sepehr Assadi Xiaorui Sun and Omri Weinstein. 2018. Massively parallel algo-rithms for finding well-connected components in sparse graphs.arXiv preprintar Xiv:1805.02974(2018)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_9_1","volume-title":"Announcement: Semi-Map Reduce Meets Congested Clique. arXiv preprintar Xiv:1802.10297(2018).","author":"Behnezhad Soheil","year":"2018","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , and Mohammad Taghi Hajiaghayi . 2018 .Brief Announcement: Semi-Map Reduce Meets Congested Clique. arXiv preprintar Xiv:1802.10297(2018). Soheil Behnezhad, Mahsa Derakhshan, and Mohammad Taghi Hajiaghayi. 2018.Brief Announcement: Semi-Map Reduce Meets Congested Clique. arXiv preprintar Xiv:1802.10297(2018)."},{"key":"e_1_3_2_1_10_1","volume-title":"Mohammad Taghi Hajiaghayi, and Richard M Karp","author":"Behnezhad Soheil","year":"2018","unstructured":"Soheil Behnezhad , Mahsa Derakhshan , Mohammad Taghi Hajiaghayi, and Richard M Karp . 2018 . Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. arXiv preprint arXiv:1807.06701(2018). Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, and Richard M Karp. 2018. Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. arXiv preprint arXiv:1807.06701(2018)."},{"key":"e_1_3_2_1_11_1","volume-title":"Mohammad Taghi Hajiaghayi, and David G Harris","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad , Mohammad Taghi Hajiaghayi, and David G Harris . 2019 . Exponentially Faster Massively Parallel Maximal Matching .arXiv preprintarXiv:1901.03744(2019). Soheil Behnezhad, Mohammad Taghi Hajiaghayi, and David G Harris. 2019. Exponentially Faster Massively Parallel Maximal Matching.arXiv preprintarXiv:1901.03744(2019)."},{"key":"e_1_3_2_1_12_1","unstructured":"Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. arXiv preprintar Xiv:1807.05374(2018).  Sebastian Brandt Manuela Fischer and Jara Uitto. 2018. Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model. arXiv preprintar Xiv:1807.05374(2018)."},{"key":"e_1_3_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms , Third Edition(3rd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition(3rd ed.). The MIT Press."},{"key":"e_1_3_2_1_14_1","volume-title":"Algorithms and Techniques (APPROX\/RANDOM2014)","volume":"28","author":"Crouch Michael","unstructured":"Michael Crouch and Daniel M. Stubbs . 2014. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. In Approximation, Randomization,and Combinatorial Optimization . Algorithms and Techniques (APPROX\/RANDOM2014) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 28 . 96--104. Michael Crouch and Daniel M. Stubbs. 2014. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. In Approximation, Randomization,and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM2014) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 28. 96--104."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation","volume":"6","author":"Dean Jeffrey","year":"2004","unstructured":"Jeffrey Dean and Sanjay Ghemawat . 2004 . Map Reduce: Simplified Data Processing on Large Clusters . In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation , Volume 6 (OSDI'04). USENIX Association, Berkeley, CA, USA, 10--10. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264 Jeffrey Dean and Sanjay Ghemawat. 2004. Map Reduce: Simplified Data Processing on Large Clusters. In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation, Volume 6 (OSDI'04). USENIX Association, Berkeley, CA, USA, 10--10. http:\/\/dl.acm.org\/citation.cfm?id=1251254.1251264"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226239.3226375"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_19_1","unstructured":"Buddhima Gamlath Sagar Kale Slobodan Mitrovic and Ola Svensson. 2018.Weighted Matchings via Unweighted Augmentations. CoRRabs\/1811.02760(2018). arXiv:1811.02760 http:\/\/arxiv.org\/abs\/1811.02760  Buddhima Gamlath Sagar Kale Slobodan Mitrovic and Ola Svensson. 2018.Weighted Matchings via Unweighted Augmentations. CoRRabs\/1811.02760(2018). arXiv:1811.02760 http:\/\/arxiv.org\/abs\/1811.02760"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310534"},{"key":"e_1_3_2_1_22_1","volume-title":"2nd Symposium on Simplicity in Algorithms. arXiv:1701","author":"Ghaffari Mohsen","year":"2019","unstructured":"Mohsen Ghaffari and David Wajc . 2019 . Simplified and Space-Optimal Semi-Streaming (2+\u03b5)-Approximate Matching . In 2nd Symposium on Simplicity in Algorithms. arXiv:1701 .03730 Mohsen Ghaffari and David Wajc. 2019. Simplified and Space-Optimal Semi-Streaming (2+\u03b5)-Approximate Matching. In 2nd Symposium on Simplicity in Algorithms. arXiv:1701.03730"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Nicholas JA Harvey Christopher Liaw and Paul Liu. 2018. Greedy and Local Ratio Algorithms in the Map Reduce Model. arXiv preprint arXiv:1806.06421(2018).  Nicholas JA Harvey Christopher Liaw and Paul Liu. 2018. Greedy and Local Ratio Algorithms in the Map Reduce Model. arXiv preprint arXiv:1806.06421(2018).","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"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.1016\/0020-0190(86)90141-9"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627938"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"Karloff Howard J.","year":"2010","unstructured":"Howard J. Karloff , Siddharth Suri , and Sergei Vassilvitskii . 2010 . A Model of Computation for Map Reduce . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA , January 17-19,2010. 938--948. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. 2010. A Model of Computation for Map Reduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19,2010. 938--948."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_3_2_1_33_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Konrad Christian","unstructured":"Christian Konrad , Fr\u00e9d\u00e9ric Magniez , and Claire Mathieu . 2012. Maximum Matching in Semi-Streaming with Few Passes . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , Vol. 7408 . Springer , 231.http:\/\/arxiv.org\/abs\/1112.0184 Christian Konrad, Fr\u00e9d\u00e9ric Magniez, and Claire Mathieu. 2012. Maximum Matching in Semi-Streaming with Few Passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Vol. 7408. Springer, 231.http:\/\/arxiv.org\/abs\/1112.0184"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835772"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777428"},{"key":"e_1_3_2_1_38_1","first-page":"565","article-title":"On determinants, matchings, and random algorithms","volume":"79","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979 . On determinants, matchings, and random algorithms .. In FCT , Vol. 79. 565 -- 574 . L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms.. In FCT, Vol. 79. 565--574.","journal-title":"FCT"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"key":"e_1_3_2_1_42_1","unstructured":"Krzysztof Onak. 2018. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. arXiv preprint arXiv:1807.08745(2018).  Krzysztof Onak. 2018. Round Compression for Parallel Graph Algorithms in Strongly Sublinear Space. arXiv preprint arXiv:1807.08745(2018)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039826"},{"key":"e_1_3_2_1_44_1","volume-title":"Hadoop: The Definitive Guide","author":"White Tom","year":"2012","unstructured":"Tom White . 2012 . Hadoop: The Definitive Guide . O'Reilly Media, Inc. Tom White. 2012. Hadoop: The Definitive Guide. O'Reilly Media, Inc."},{"key":"e_1_3_2_1_45_1","volume-title":"Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud'10","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud'10 , Boston, MA, USA, June22. https:\/\/www.usenix.org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud'10, Boston, MA, USA, June22. https:\/\/www.usenix.org\/conference\/hotcloud-10\/spark-cluster-computing-working-sets"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:02Z","timestamp":1750208522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":45,"alternative-id":["10.1145\/3293611.3331603","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331603","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}