论文标题
确定性的婴儿车近似近似路径的路径和稍微超级线性的工作
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work
论文作者
论文摘要
我们研究了$（1+ε）$ - 在$ n $ vertex中以平行（PRAM）计算模型中的$ n $ vertex中的$ n $ vertex中的近似单源最短路径（从此以后，$（1+ε）$ -SSSP）。 Cohen [cohen94]给出了一种带有聚类时间和略微超级线性工作的随机算法，用于任意的$ρ> 0 $，$ \ tilde {o}（| e | e | \ cdot n^ρ）$比$ 25 $ 25美元。 近年来取得了令人兴奋的进展[Elkinn17，Elkinn19，li19，andonisz19]，最终以随机的聚类时间和$ \ tilde {o}（| e |）$工作。但是，是否存在Cohen算法的确定性同行的问题仍然很开放。 在当前论文中，我们为此基本问题设计了第一个确定性的pologarithmic-time算法，其中有工作$ \ tilde {o}（| e | \ cdot n^ρ）$，用于任意的小$ρ> 0 $。该结果基于我们在本文中设计的第一个有效的确定性并行算法。
We study a $(1+ε)$-approximate single-source shortest paths (henceforth, $(1+ε)$-SSSP) in $n$-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A randomized algorithm with polylogarithmic time and slightly super-linear work $\tilde{O}(|E|\cdot n^ρ)$, for an arbitrarily small $ρ>0$, was given by Cohen [Coh94] more than $25$ years ago. Exciting progress on this problem was achieved in recent years [ElkinN17,ElkinN19,Li19,AndoniSZ19], culminating in randomized polylogarithmic time and $\tilde{O}(|E|)$ work. However, the question of whether there exists a deterministic counterpart of Cohen's algorithm remained wide open. In the current paper we devise the first deterministic polylogarithmic-time algorithm for this fundamental problem, with work $\tilde{O}(|E|\cdot n^ρ)$, for an arbitrarily small $ρ>0$. This result is based on the first efficient deterministic parallel algorithm for building hopsets, which we devise in this paper.
