Parallel approximate undirected shortest paths via low hop emulators
Parallel approximate undirected shortest paths via low hop emulators
复制标题
通过低跳模拟器并行近似无向最短路径
DOI：
10.1145/3357713.3384321
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhong, Peilin
中科院分区：
文献类型：
--
作者：
Andoni, Alexandr;Stein, Clifford;Zhong, Peilin
本文提出了一个计算无向图最短路的（1+ε）-近似并行算法，其中poly（logn）depth和mppoly（logn）算法适用于n-节点m-边图.虽然具有（接近）最优运行时间的顺序算法已经存在了几十年，但接近最优的并行算法已经成为一个更严峻的挑战。对于（1+ε）-近似，所有具有poly（logn）深度的现有算法对于某个常数tc>0至少执行Ω（mnc）工作。Cohen（STOC'94）提出的这个长期存在的上界的改进已经开放了25年。其中之一是超越跳集的新概念--低跳模拟器--一个多（logn）-近似模拟器图，其中每条最短路径至多有O（loglogn）跳（边）。低跳模拟器的直接应用是poly（logn）-近似单源最短路径（SSSP）、Bourgain嵌入、度量树嵌入和低直径分解的并行算法，所有这些算法都具有poly（logn）深度和mppoly（logn）工作。我们引入了可压缩预处理器并将其应用于谢尔曼的框架（SODA'17）中以解决无容量限制的最小成本流的更一般的问题（也称为，转运问题）。我们的算法使用mpoly（logn）功在poly（logn）深度上计算一个（1+ε）-近似无容量限制的最小费用流。因此，它还改进了最先进的顺序运行时间从mm·2 O（logn）到poly（logn）。
We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achievingpoly(logn) depth andmpoly(logn) work forn-nodesm-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1+ε)-approximation, all prior algorithms withpoly(logn) depth perform at least Ω(mnc) work for some constantc>0. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.We develop several new tools of independent interest. One of them is a new notion beyond hopsets — low hop emulator — apoly(logn)-approximate emulator graph in which every shortest path has at mostO(loglogn) hops (edges). Direct applications of the low hop emulators are parallel algorithms forpoly(logn)-approximate single source shortest path (SSSP), Bourgain’s embedding, metric tree embedding, and low diameter decomposition, all withpoly(logn) depth andmpoly(logn) work.To boost the approximation ratio to (1+ε), we introduce compressible preconditioners and apply it inside Sherman’s framework (SODA’17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a (1+ε)-approximate uncapacitated minimum cost flow inpoly(logn) depth usingmpoly(logn) work. As a consequence, it also improves the state-of-the-art sequential running time fromm· 2O(√logn)tompoly(logn).
登录
查看更多内容
DOI：
10.1145/800222.806745
发表时间：
1984-08
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Faith Ellen;P. Ragde;A. Wigderson
通讯作者：
Faith Ellen;P. Ragde;A. Wigderson
简短公告：Semi-MapReduce 遇到拥堵派系
DOI：
--
发表时间：
2018
期刊：
arXiv.org
影响因子：
--
作者：
Soheil Behnezhad;Mahsa Derakhshan;M. Hajiaghayi
通讯作者：
M. Hajiaghayi
简短公告：大规模并行近似距离草图
DOI：
--
发表时间：
2019
期刊：
International Symposium on Distributed Computing
影响因子：
--
作者：
M. Dinitz;Yasamin Nazari
通讯作者：
Yasamin Nazari
DOI：
10.1006/jagm.1997.0888
发表时间：
1997
期刊：
J. Algorithms
影响因子：
--
作者：
P. Klein;Sairam Subramanian
通讯作者：
Sairam Subramanian
近似最短路径的更快并行算法
DOI：
--
发表时间：
2019
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Jason Li
通讯作者：
Jason Li