



























This paper presents an $O(\log\log \bar{d})$ round massively parallel algorithm for $1+ε$ approximation of maximum weighted $b$-matchings, using near-linear memory per machine. Here $\bar{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(\log\log n)$, or $O(\log\log Δ)$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。