{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:18Z","timestamp":1750309458259,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T00:00:00Z","timestamp":1735948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1955939"],"award-info":[{"award-number":["1955939"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Council of Finland Grant 334238, Helsinki Institute for Information Technology (HIIT)","award":["334238"],"award-info":[{"award-number":["334238"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,1,4]]},"DOI":"10.1145\/3700838.3700861","type":"proceedings-article","created":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T12:58:12Z","timestamp":1735822692000},"page":"144-151","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Faster Set Cover in the MPC Model"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6610-844X","authenticated-orcid":false,"given":"Hongyan","family":"Ji","sequence":"first","affiliation":[{"name":"The University of Iowa, Iowa City, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2409-7807","authenticated-orcid":false,"given":"Shreyas","family":"Pai","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0834-3476","authenticated-orcid":false,"given":"Sriram","family":"Pemmaraju","sequence":"additional","affiliation":[{"name":"The University of Iowa, Iowa City, United States"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7482-0754","authenticated-orcid":false,"given":"Joshua","family":"Sobel","sequence":"additional","affiliation":[{"name":"The University of Iowa, Iowa City, United States"}]}],"member":"320","published-online":{"date-parts":[[2025,1,4]]},"reference":[{"key":"e_1_3_3_2_2_2","doi-asserted-by":"publisher","unstructured":"Noga Alon L\u00e1szl\u00f3 Babai and Alon Itai. 1986. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. J. Algorithms 7 4 (dec 1986) 567\u2013583. 10.1016\/0196-6774(86)90019-2","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80068-6"},{"key":"e_1_3_3_2_5_2","doi-asserted-by":"publisher","unstructured":"Keren Censor-Hillel and Michal Dory. 2021. Distributed Spanner Approximation. SIAM J. Comput. 50 3 (2021) 1103\u20131147. 10.1137\/20M1312630 arXiv:10.1137\/20M1312630","DOI":"10.1137\/20M1312630"},{"key":"e_1_3_3_2_6_2","doi-asserted-by":"publisher","unstructured":"V. Chvatal. 1979. A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res. 4 3 (aug 1979) 233\u2013235. 10.1287\/moor.4.3.233","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_3_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400282"},{"key":"e_1_3_3_2_8_2","doi-asserted-by":"publisher","unstructured":"Artur Czumaj Peter Davies and Merav Parter. 2021. Simple Deterministic Constant-Round Coloring in Congested Clique and MPC. SIAM J. Comput. 50 5 (2021) 1603\u20131626. 10.1137\/20M1366502 arXiv:10.1137\/20M1366502","DOI":"10.1137\/20M1366502"},{"key":"e_1_3_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Artur Czumaj Jakub \u0141\u0105cki Aleksander M\u0105dry Slobodan Mitrovi\u0107 Krzysztof Onak and Piotr Sankowski. 2018. Round compression for parallel matching algorithms. Proceedings of the Annual ACM Symposium on Theory of Computing 14 1 (2018) 471\u2013484.","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2024.19"},{"key":"e_1_3_3_2_11_2","unstructured":"Laxman Dhulipala Michael Dinitz Jakub \u0141\u0105cki and Slobodan Mitrovi\u0107. 2024. Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling. arxiv:https:\/\/arXiv.org\/abs\/2408.13362\u00a0[cs.DS] https:\/\/arxiv.org\/abs\/2408.13362"},{"key":"e_1_3_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_3_2_13_2","doi-asserted-by":"publisher","unstructured":"Jon Feldman S. Muthukrishnan Anastasios Sidiropoulos Cliff Stein and Zoya Svitkina. 2010. On Distributing Symmetric Streaming Computations. ACM Trans. Algorithms 6 4 Article 66 (sep 2010) 19\u00a0pages. 10.1145\/1824777.1824786","DOI":"10.1145\/1824777.1824786"},{"key":"e_1_3_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087830"},{"key":"e_1_3_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-89240-1_7"},{"key":"e_1_3_3_2_19_2","doi-asserted-by":"crossref","unstructured":"Christoph Grunau Slobodan Mitrovic Ronitt Rubinfeld and Ali Vakilian. 2019. Improved Local Computation Algorithm for Set Cover via Sparsification. CoRR abs\/1910.14154 (2019) 2993\u20133011. arXiv:https:\/\/arXiv.org\/abs\/1910.14154http:\/\/arxiv.org\/abs\/1910.14154","DOI":"10.1137\/1.9781611975994.181"},{"key":"e_1_3_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.181"},{"key":"e_1_3_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_35"},{"key":"e_1_3_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Lujun Jia Rajmohan Rajaraman and Torsten Suel. 2002. An efficient distributed algorithm for constructing small dominating sets. Distributed Comput. 15 4 (2002) 193\u2013205. 10.1007\/s00446-002-0078-0","DOI":"10.1007\/s00446-002-0078-0"},{"key":"e_1_3_3_2_24_2","doi-asserted-by":"publisher","unstructured":"David\u00a0S. Johnson. 1974. Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci. 9 3 (dec 1974) 256\u2013278. 10.1016\/S0022-0000(74)80044-9","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.28"},{"key":"e_1_3_3_2_27_2","doi-asserted-by":"publisher","unstructured":"L. Lov\u00e1sz. 1975. On the Ratio of Optimal Integral and Fractional Covers. Discrete Math. 13 4 (jan 1975) 383\u2013390. 10.1016\/0012-365X(75)90058-8","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_3_3_2_28_2","doi-asserted-by":"publisher","unstructured":"Michael Luby. 1986. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15 4 (1986) 1036\u20131053. 10.1137\/0215074 arXiv:10.1137\/0215074","DOI":"10.1137\/0215074"},{"key":"e_1_3_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.40"},{"key":"e_1_3_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Sridhar Rajagopalan and Vijay\u00a0V. Vazirani. 1999. Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. SIAM J. Comput. 28 2 (feb 1999) 525\u2013540. 10.1137\/S0097539793260763","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_3_3_2_32_2","series-title":"Proceedings of Machine Learning Research","first-page":"5600","volume-title":"Proceedings of the 35th International Conference on Machine Learning","volume":"80","author":"Yaroslavtsev Grigory","year":"2018","unstructured":"Grigory Yaroslavtsev and Adithya Vadapalli. 2018. Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under \u2113p Distances. In Proceedings of the 35th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol.\u00a080), Jennifer Dy and Andreas Krause (Eds.). PMLR, US, 5600\u20135609. https:\/\/proceedings.mlr.press\/v80\/yaroslavtsev18a.html"}],"event":{"name":"ICDCN 2025: 26th International Conference on Distributed Computing and Networking","acronym":"ICDCN 2025","location":"Hyderabad India"},"container-title":["Proceedings of the 26th International Conference on Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700838.3700861","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700838.3700861","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3700838.3700861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:22Z","timestamp":1750295422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3700838.3700861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,4]]},"references-count":31,"alternative-id":["10.1145\/3700838.3700861","10.1145\/3700838"],"URL":"https:\/\/doi.org\/10.1145\/3700838.3700861","relation":{},"subject":[],"published":{"date-parts":[[2025,1,4]]},"assertion":[{"value":"2025-01-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}