论文标题
$ b $匹配的大规模并行算法
Massively Parallel Algorithms for $b$-Matching
论文作者
论文摘要
本文介绍了$ o（\ log \ log \ bar {d}）$圆形并行算法，$ 1+ε$ $ to的最大加权$ b $匹配的近似值，使用近乎线性的每台机器。这里$ \ bar {d} $表示图中的平均程度，$ε$是任意小的正常常数。回想一下，$ b $ - 匹配是匹配问题的自然且研究的概括，在匹配中，不同的顶点可以在匹配中具有多个（且数量不同的）事件边缘。具体而言，每个顶点$ v $都会给出一个正整数预算$ b_v $，并且在匹配中最多可以具有$ b_v $事件边缘。以前，有圆形复杂性$ o（\ log \ log \ log n）$的已知算法，或$ o（\ log \logδ）$，其中$δ$表示最高学位，以$ 1+ε$的加权匹配和最大匹配[Czumaj et al。，Stoc'18，stoc'18，Ghaffari等。 podc'18; Assadi等。 Soda'19; Behnezhad等。焦点19; Gamlath等。 PODC'19]，但是这些算法并未扩展到更通用的$ b $匹配问题。
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.
