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 Õ(√log λ) 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.