Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916780554846208 |
|---|---|
| author | Łącki, Jakub Mitrović, Slobodan Ramachandran, Srikkanth Sheu, Wen-Horng |
| author_facet | Łącki, Jakub Mitrović, Slobodan Ramachandran, Srikkanth Sheu, Wen-Horng |
| contents | We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of $b$-matching, in which the input is a bipartite graph with capacities greater than $1$ in only one part of the bipartition. We give a $(1+ε)$ approximate algorithm for the problem, which runs in $\tilde{O}(\sqrt{\log λ})$ MPC rounds, using sublinear space per machine and $\tilde{O}(λn)$ total space, where $λ$ is the arboricity of the input graph. Our result is obtained by providing a new analysis of a LOCAL algorithm by Agrawal, Zadimoghaddam, and Mirrokni [ICML 2018], which improves its round complexity from $O(\log n)$ to $O(\log λ)$. Prior to our work, no $o(\log n)$ round algorithm for constant-approximate allocation was known in either LOCAL or sublinear space MPC models for graphs with low arboricity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04524 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs Łącki, Jakub Mitrović, Slobodan Ramachandran, Srikkanth Sheu, Wen-Horng Data Structures and Algorithms We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of $b$-matching, in which the input is a bipartite graph with capacities greater than $1$ in only one part of the bipartition. We give a $(1+ε)$ approximate algorithm for the problem, which runs in $\tilde{O}(\sqrt{\log λ})$ MPC rounds, using sublinear space per machine and $\tilde{O}(λn)$ total space, where $λ$ is the arboricity of the input graph. Our result is obtained by providing a new analysis of a LOCAL algorithm by Agrawal, Zadimoghaddam, and Mirrokni [ICML 2018], which improves its round complexity from $O(\log n)$ to $O(\log λ)$. Prior to our work, no $o(\log n)$ round algorithm for constant-approximate allocation was known in either LOCAL or sublinear space MPC models for graphs with low arboricity. |
| title | Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.04524 |