{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:46Z","timestamp":1777954606063,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","funder":[{"name":"Google Research Scholar"},{"name":"NSF Faculty Early Career Development Program","award":["2340048"],"award-info":[{"award-number":["2340048"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743319","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"339-349","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9347-0041","authenticated-orcid":false,"given":"Jakub","family":"\u0141\u0105cki","sequence":"first","affiliation":[{"name":"Google Research, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9269-4379","authenticated-orcid":false,"given":"Slobodan","family":"Mitrovi\u0107","sequence":"additional","affiliation":[{"name":"UC Davis, Davis, USA, University of Novi Sad, Novi Sad, Serbia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2392-1999","authenticated-orcid":false,"given":"Srikkanth","family":"Ramachandran","sequence":"additional","affiliation":[{"name":"UC Davis, Davis, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2707-8612","authenticated-orcid":false,"given":"Wen-Horng","family":"Sheu","sequence":"additional","affiliation":[{"name":"UC Davis, Davis, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"Proceedings of Machine Learning Research","first-page":"99","volume-title":"Jennifer G. Dy and Andreas Krause","author":"Agrawal Shipra","year":"2018","unstructured":"Shipra Agrawal, Morteza Zadimoghaddam, and Vahab S. Mirrokni. Proportional allocation: Simple, distributed, and diverse matching with high entropy. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 99--108. PMLR, 2018. URL: http:\/\/proceedings.mlr.press\/v80\/agrawal18b.html."},{"key":"e_1_3_2_1_2_1","volume-title":"12th Innovations in Theoretical Computer Science Conference (ITCS 2021","author":"Ahmadian Sara","year":"2021","unstructured":"Sara Ahmadian, Allen Liu, Binghui Peng, and Morteza Zadimoghaddam. Distributed load balancing: A new framework and improved guarantees. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2021."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22832-2"},{"key":"e_1_3_2_1_4_1","first-page":"1616","volume-title":"Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1616--1635. SIAM, 2019."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2242"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00096"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467903"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284177"},{"key":"e_1_3_2_1_12_1","first-page":"19","volume-title":"38th International Symposium on Distributed Computing (DISC 2024","author":"Dhulipala Laxman","year":"2024","unstructured":"Laxman Dhulipala, Michael Dinitz, Jakub \u0141\u0105cki, and Slobodan Mitrovi\u0107. Parallel set cover and hypergraph matching via uniform random sampling. In 38th International Symposium on Distributed Computing (DISC 2024), pages 19--1. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456756"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.34"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538589"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"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","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835772"},{"key":"e_1_3_2_1_25_1","volume-title":"Scalable auction algorithms for bipartite maximum matching problems. arXiv preprint arXiv:2307.08979","author":"Liu Quanquan C","year":"2023","unstructured":"Quanquan C Liu, Yiduo Ke, and Samir Khuller. Scalable auction algorithms for bipartite maximum matching problems. arXiv preprint arXiv:2307.08979, 2023."},{"key":"e_1_3_2_1_26_1","volume-title":"Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es","author":"Mehta Aranyak","year":"2007","unstructured":"Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807360"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2015.7295474"},{"key":"e_1_3_2_1_29_1","volume-title":"Learning robust algorithms for online allocation problems using adversarial training. CoRR, abs\/2010.08418","author":"Zuzic Goran","year":"2020","unstructured":"Goran Zuzic, Di Wang, Aranyak Mehta, and D. Sivakumar. Learning robust algorithms for online allocation problems using adversarial training. CoRR, abs\/2010.08418, 2020. URL: https:\/\/arxiv.org\/abs\/2010.08418, arXiv:2010.08418."},{"key":"e_1_3_2_1_30_1","volume-title":"Faster MPC algorithms for approximate allocation in uniformly sparse graphs. CoRR, abs\/2506.04524","author":"\u0141\u0105cki Jakub","year":"2025","unstructured":"Jakub \u0141\u0105cki, Slobodan Mitrovi\u0107, Srikkanth Ramachandran, and Wen-Horng Sheu. Faster MPC algorithms for approximate allocation in uniformly sparse graphs. CoRR, abs\/2506.04524, 2025. URL: https:\/\/arxiv.org\/abs\/2506.04524, arXiv:2506.04524."}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:13Z","timestamp":1777922353000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":30,"alternative-id":["10.1145\/3694906.3743319","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743319","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}