Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs

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 Õ (√long λ) MPC rounds, using sublinear space per machine and Õ (λ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.