Massively Parallel Algorithms for b-Matching
share
This paper presents an O(loglogd̅) round massively parallel algorithm for 1+ϵ approximation of maximum weighted b-matchings, using near-linear memory per machine. Here d̅ denotes the average degree in the graph and ϵ is an arbitrarily small positive constant. Recall that b-matching is the natural and well-studied generalization of the matching problem where different vertices are allowed to have multiple (and differing number of) incident edges in the matching. Concretely, each vertex v is given a positive integer budget b_v and it can have up to b_v incident edges in the matching. Previously, there were known algorithms with round complexity O(loglog n), or O(loglogΔ) where Δ denotes maximum degree, for 1+ϵ approximation of weighted matching and for maximal matching [Czumaj et al., STOC'18, Ghaffari et al. PODC'18; Assadi et al. SODA'19; Behnezhad et al. FOCS'19; Gamlath et al. PODC'19], but these algorithms do not extend to the more general b-matching problem.
READ FULL TEXT