论文标题
无方向的$（1+ \ varepsilon）$ - 少数聚集的最短路径：近乎最佳的确定性并行和分布式算法
Undirected $(1+\varepsilon)$-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms
论文作者
论文摘要
本文介绍了用于计算$（1+ \ varepsilon）$的近乎最佳的确定性平行算法和分布式算法 - 在任何无方向的加权图中，近似单源路径近似最短的路径。 在高水平上，我们决定将此问题和其他最短路径的问题减少到$ \ tilde {o}（1）$ sill-grogegations。次要聚集会计算某些子图的每个连接组件的节点值的聚合（例如，最大或总和）。 我们的减少立即暗示： 具有$ \ tilde {o}（1）$深度和近线性工作的最佳确定性并行（PRAM）算法。 每当存在确定性的小型聚集算法时，普遍最佳的确定性分布式分布式算法。例如，最佳$ \ tilde {o}（hopdiameter（g））$ - 圆形确定性拥塞算法，用于排除少量网络。 为上述结果开发的几种新颖的工具本身很有趣： 将最短路径计算“最大距离$ d $”减少到低直径分解为“距离$ \ frac {d} {2} $”的本地迭代方法。与[LI20]的递归顶点减少方法相比，我们的方法更简单，适合分布式算法，并消除了许多偏差屏障。 一个简单的基于图的$ \ tilde {o}（1）$ - 竞争性$ \ ell_1 $ - 基于低直径分解的路由，可以在近乎线性的工作中评估。以前的此类路由[ZGY+20]为$ n^{o（1）} $ - 竞争性，需要$ n^{o（1）} $更多工作。 确定性算法将任何分数单源转运流动到整体树解决方案中。 用于计算欧拉方向的第一个分布式算法。
This paper presents near-optimal deterministic parallel and distributed algorithms for computing $(1+\varepsilon)$-approximate single-source shortest paths in any undirected weighted graph. On a high level, we deterministically reduce this and other shortest-path problems to $\tilde{O}(1)$ Minor-Aggregations. A Minor-Aggregation computes an aggregate (e.g., max or sum) of node-values for every connected component of some subgraph. Our reduction immediately implies: Optimal deterministic parallel (PRAM) algorithms with $\tilde{O}(1)$ depth and near-linear work. Universally-optimal deterministic distributed (CONGEST) algorithms, whenever deterministic Minor-Aggregate algorithms exist. For example, an optimal $\tilde{O}(HopDiameter(G))$-round deterministic CONGEST algorithm for excluded-minor networks. Several novel tools developed for the above results are interesting in their own right: A local iterative approach for reducing shortest path computations "up to distance $D$" to computing low-diameter decompositions "up to distance $\frac{D}{2}$". Compared to the recursive vertex-reduction approach of [Li20], our approach is simpler, suitable for distributed algorithms, and eliminates many derandomization barriers. A simple graph-based $\tilde{O}(1)$-competitive $\ell_1$-oblivious routing based on low-diameter decompositions that can be evaluated in near-linear work. The previous such routing [ZGY+20] was $n^{o(1)}$-competitive and required $n^{o(1)}$ more work. A deterministic algorithm to round any fractional single-source transshipment flow into an integral tree solution. The first distributed algorithms for computing Eulerian orientations.
