论文标题
通过跳闸和矩形矩阵乘法的集中，平行和分布的多源最短路径
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication
论文作者
论文摘要
考虑一个无方向的加权图$ g =（v，e，w）$。我们研究计算$（1+ε）$的问题 - $ s \ times v $的近似最短路径，对于子集$ s \ subseteq v $ $ | s | = n^r $来源，对于$ 0 <r \ le 1 $。我们在整个参数$ r $的范围内，在经典的集中式和平行（PRAM）计算模型中，在整个参数$ r $的范围内都为此问题设计了一个显着改进的算法，并且在分布式（拥挤的集团）模型中均以$ r $ $ r $的范围。具体而言，我们针对此问题的集中算法需要时间$ \ tilde {o}（| e | \ cdot n^{o（1）} + n^{ω（r）}）$，其中$ n^{ω（ω（r）} $是乘以乘以a $ n^r \ n^r \ time n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n y $ n $所需的时间。我们的婴儿车算法具有polygarithmic Time $（\ log n）^{o（1/ρ）} $，其工作复杂性为$ \ tilde {o}（| e | e | \ cdot n^ρ+ n^ρ+ n^{ω（R）}（ω（r）}）$ 特别是，对于$ r \ le 0.313 \ ldots $，我们的集中式算法计算$ s \ times v $ $（1 +ε）$ - $ n^{2 + o（1）} $ time的近似最短路径。对于任何任意的小常数$ρ> 0 $，我们的PRAM POLYOGAROGAROGARITHMICTIME算法具有工作复杂度$ O（| e | \ cdot n^ρ+ n^{2+ o（1）}）$。以前现有的解决方案需要$ O（| e | \ cdot | s |）$的集中时间/并行工作，或提供弱近似保证。 在拥挤的集团模型中，我们的算法在$ | s |中解决了polyogarithmic的问题。 = n^r $源，对于$ r \ le 0.655 $，而以前的最先进算法仅对$ r \ le 1/2 $这样做。此外，它改善了所有$ r> 1/2 $的先前界限。对于未加权图，运行时间将进一步提高到$ poly（\ log \ log n）$。
Consider an undirected weighted graph $G = (V,E,w)$. We study the problem of computing $(1+ε)$-approximate shortest paths for $S \times V$, for a subset $S \subseteq V$ of $|S| = n^r$ sources, for some $0 < r \le 1$. We devise a significantly improved algorithm for this problem in the entire range of parameter $r$, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of $r$ in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time $\tilde{O}(|E| \cdot n^{o(1)} + n^{ω(r)})$, where $n^{ω(r)}$ is the time required to multiply an $n^r \times n$ matrix by an $n \times n$ one. Our PRAM algorithm has polylogarithmic time $(\log n)^{O(1/ρ)}$, and its work complexity is $\tilde{O}(|E| \cdot n^ρ+ n^{ω(r)})$, for any arbitrarily small constant $ρ>0$. In particular, for $r \le 0.313\ldots$, our centralized algorithm computes $S \times V$ $(1+ε)$-approximate shortest paths in $n^{2 + o(1)}$ time. Our PRAM polylogarithmic-time algorithm has work complexity $O(|E| \cdot n^ρ+ n^{2+o(1)})$, for any arbitrarily small constant $ρ>0$. Previously existing solutions either require centralized time/parallel work of $O(|E| \cdot |S|)$ or provide much weaker approximation guarantees. In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for $|S| = n^r$ sources, for $r \le 0.655$, while previous state-of-the-art algorithms did so only for $r \le 1/2$. Moreover, it improves previous bounds for all $r > 1/2$. For unweighted graphs, the running time is improved further to $poly(\log\log n)$.
