Massively Parallel Algorithms for $b$-Matching

Mohsen Ghaffari, Christoph Grunau, Slobodan Mitrović

This paper presents an $O(\log \log \bar{d})$ round massively parallel algorithm for $1+\epsilon$ approximation of maximum weighted $b$-matchings, using near-linear memory per machine. Her…