论文标题
最小重量顶点盖的大量平行算法
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
论文作者
论文摘要
我们提出了一种大规模并行算法，每台机器具有接近线性的内存，该算法计算$（2+ \ varepsilon）$ - 最小重量顶点封面的近似值（\ log \ log \ log \ log \ log \ log \ log \ log d）$ rounds，其中$ d $是输入图的平均程度。 我们的结果填补了有关顶点覆盖和匹配问题的最先进MPC算法中剩余的剩余差距；两个经典的优化问题，它们是彼此双重的。具体而言，Czumaj等人最近的工作 - - 。 [Stoc'18]，Ghaffari等。 [PODC'18]，Assadi等。 [Soda'19]和Gamlath等。 [PODC'19] ---提供$ O（\ log \ log n）$（1+ \ Varepsilon）$的时间算法 - 大约最大重量匹配，以及$（2+ \ varepsilon）$ - 近似的最小基数角度顶点封面。但是，后一种算法对顶点盖的一般加权案例不起作用，为此，最著名的算法仍处于$ O（\ log n）$时间复杂性。
We present a massively parallel algorithm, with near-linear memory per machine, that computes a $(2+\varepsilon)$-approximation of minimum-weight vertex cover in $O(\log\log d)$ rounds, where $d$ is the average degree of the input graph. Our result fills the key remaining gap in the state-of-the-art MPC algorithms for vertex cover and matching problems; two classic optimization problems, which are duals of each other. Concretely, a recent line of work---by Czumaj et al. [STOC'18], Ghaffari et al. [PODC'18], Assadi et al. [SODA'19], and Gamlath et al. [PODC'19]---provides $O(\log\log n)$ time algorithms for $(1+\varepsilon)$-approximate maximum weight matching as well as for $(2+\varepsilon)$-approximate minimum cardinality vertex cover. However, the latter algorithm does not work for the general weighted case of vertex cover, for which the best known algorithm remained at $O(\log n)$ time complexity.
