{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:24Z","timestamp":1750221144039,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,11]],"date-time":"2018-07-11T00:00:00Z","timestamp":1531267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,11]]},"DOI":"10.1145\/3210377.3210386","type":"proceedings-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T17:46:44Z","timestamp":1531417604000},"page":"43-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Greedy and Local Ratio Algorithms in the MapReduce Model"],"prefix":"10.1145","author":[{"given":"Nicholas J. A.","family":"Harvey","sequence":"first","affiliation":[{"name":"University of British Columbia, Vancouver, BC, Canada"}]},{"given":"Christopher","family":"Liaw","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, BC, Canada"}]},{"given":"Paul","family":"Liu","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_2_1_2_1","volume-title":"Simple Round Compression for Parallel Vertex Cover. arXiv preprint arXiv:1709.04599","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi . 2017. Simple Round Compression for Parallel Vertex Cover. arXiv preprint arXiv:1709.04599 ( 2017 ). Sepehr Assadi. 2017. Simple Round Compression for Parallel Vertex Cover. arXiv preprint arXiv:1709.04599 (2017)."},{"key":"e_1_3_2_1_3_1","volume-title":"Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint arXiv:1711","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab Mirrokni , and Cliff Stein . 2017 . Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint arXiv:1711 .03076 (2017). Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. 2017. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. arXiv preprint arXiv:1711.03076 (2017)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087581"},{"key":"e_1_3_2_1_5_1","unstructured":"Maria-Florina Balcan Steven Ehrlich and Yingyu Liang. 2013. Distributed kmeans and k-median clustering on general communication topologies. In Advances in Neural Information Processing Systems (NIPS). 1995--2003.   Maria-Florina Balcan Steven Ehrlich and Yingyu Liang. 2013. Distributed kmeans and k-median clustering on general communication topologies. In Advances in Neural Information Processing Systems (NIPS). 1995--2003."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041683"},{"key":"e_1_3_2_1_7_1","first-page":"27","article-title":"A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem","volume":"25","author":"Bar-Yehuda Reuven","year":"1985","unstructured":"Reuven Bar-Yehuda and Shimon Even . 1985 . A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem . Annals of Discrete Mathematics 25 (1985), 27 -- 45 . Reuven Bar-Yehuda and Shimon Even. 1985. A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem. Annals of Discrete Mathematics 25 (1985), 27--45.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_3_2_1_8_1","unstructured":"Leonid Barenboim and Michael Elkin. 2017. Distributed Graph Coloring. Morgan & Claypool. Draft manuscript.  Leonid Barenboim and Michael Elkin. 2017. Distributed Graph Coloring. Morgan & Claypool. Draft manuscript."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80068-6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989497"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/358141.358144"},{"volume-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 96--104","author":"Crouch Michael","key":"e_1_3_2_1_14_1","unstructured":"Michael Crouch and Daniel S. Stubbs . 2014. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching . In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 96--104 . Michael Crouch and Daniel S. Stubbs. 2014. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 96--104."},{"key":"e_1_3_2_1_15_1","unstructured":"Artur Czumaj Jakub \u0141\u0105cki Aleksander M\u0105dry Slobodan Mitrovi\u0107 Krzysztof Onak and Piotr Sankowski. 2017. Round Compression for Parallel Matching Algorithms. (2017). http:\/\/arxiv.org\/abs\/1707.03478  Artur Czumaj Jakub \u0141\u0105cki Aleksander M\u0105dry Slobodan Mitrovi\u0107 Krzysztof Onak and Piotr Sankowski. 2017. Round Compression for Parallel Matching Algorithms. (2017). http:\/\/arxiv.org\/abs\/1707.03478"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_1_18_1","unstructured":"Mohsen Ghaffari. 2017. Space-Optimal Semi-Streaming for (2 + \u03b5)-Approximate Matching. (2017). http:\/\/arxiv.org\/abs\/1701.03730  Mohsen Ghaffari. 2017. Space-Optimal Semi-Streaming for (2 + \u03b5)-Approximate Matching. (2017). http:\/\/arxiv.org\/abs\/1701.03730"},{"key":"e_1_3_2_1_19_1","unstructured":"Michael T. Goodrich. 2010. Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry. (2010). http: \/\/arxiv.org\/abs\/1004.4708  Michael T. Goodrich. 2010. Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry. (2010). http: \/\/arxiv.org\/abs\/1004.4708"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_21_1","unstructured":"Elena Grigorescu Morteza Monemizadeh and Samson Zhou. 2016. Streaming Weighted Matchings: Optimal Meets Greedy. (2016). http:\/\/arxiv.org\/abs\/1608. 01487  Elena Grigorescu Morteza Monemizadeh and Samson Zhou. 2016. Streaming Weighted Matchings: Optimal Meets Greedy. (2016). http:\/\/arxiv.org\/abs\/1608. 01487"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921634"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2809814"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"volume-title":"Mining of Massive Datasets","author":"Leskovec Jure","key":"e_1_3_2_1_29_1","unstructured":"Jure Leskovec , Anand Rajaraman , and Jeff Ullman . 2014. Mining of Massive Datasets . Cambridge University Press . Jure Leskovec, Anand Rajaraman, and Jeff Ullman. 2014. Mining of Massive Datasets. Cambridge University Press."},{"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\/0215074"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90033-S"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746624"},{"key":"e_1_3_2_1_34_1","unstructured":"Baharan Mirzasoleiman Amin Karbasi Ashwinkumar Badanidiyuru and Andreas Krause. 2015. Distributed Submodular Cover: Succinctly Summarizing Massive Data. In Neural Information Processing Systems (NIPS).   Baharan Mirzasoleiman Amin Karbasi Ashwinkumar Badanidiyuru and Andreas Krause. 2015. Distributed Submodular Cover: Succinctly Summarizing Massive Data. In Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_2_1_35_1","unstructured":"Baharan Mirzasoleiman Morteza Zadimoghaddam and Andreas Krause. 2016. Fast Distributed Submodular Cover: Public-Private Data Summarization. In Neural Information Processing Systems (NIPS).   Baharan Mirzasoleiman Morteza Zadimoghaddam and Andreas Krause. 2016. Fast Distributed Submodular Cover: Public-Private Data Summarization. In Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90041-S"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039826"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783315"},{"key":"e_1_3_2_1_40_1","volume-title":"Parallel Computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science.","author":"Valiant Leslie G.","year":"1982","unstructured":"Leslie G. Valiant . 1982 . Parallel Computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. Leslie G. Valiant. 1982. Parallel Computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"volume-title":"Approximation Algorithms","author":"Vazirani Vijay V.","key":"e_1_3_2_1_42_1","unstructured":"Vijay V. Vazirani . 2001. Approximation Algorithms . Springer-Verlag New York, Inc. , New York, NY, USA . Vijay V. Vazirani. 2001. Approximation Algorithms. Springer-Verlag New York, Inc., New York, NY, USA."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"}],"event":{"name":"SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Vienna Austria","acronym":"SPAA '18"},"container-title":["Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:13Z","timestamp":1750208893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,11]]},"references-count":43,"alternative-id":["10.1145\/3210377.3210386","10.1145\/3210377"],"URL":"https:\/\/doi.org\/10.1145\/3210377.3210386","relation":{},"subject":[],"published":{"date-parts":[[2018,7,11]]},"assertion":[{"value":"2018-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}