Consider an undirected weighted graph $G = (V,E,w)$. We study the problem of computing $(1+\epsilon)$-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^{\omega(r)})$, where $n^{\omega(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/\rho)}$, and its work complexity is $\tilde{O}(|E| \cdot n^\rho + n^{\omega(r)})$, for any arbitrarily small constant $\rho >0$. In particular, for $r \le 0.313\ldots$, our centralized algorithm computes $S \times V$ $(1+\epsilon)$-approximate shortest paths in $n^{2 + o(1)}$ time. Our PRAM polylogarithmic-time algorithm has work complexity $O(|E| \cdot n^\rho + n^{2+o(1)})$, for any arbitrarily small constant $\rho >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)$.


翻译:考虑一个非方向的加权G$ = (V,E,w) 。我们研究如何计算美元(1 ⁇ epsilon) 美元最短的路径 $S\time V$, 一个子集 $S\subsete V$ $ _S = n%r美元 美元 美元。 我们设计了一个显著改进的算法, 在整个参数范围内, 无论是在传统的中央和平行计算模式(PRAM) 美元, 还是在分布式的(Conged Crique) 模式中, 美元近于美元。 具体而言, 我们的中央算法需要时间 $\ subsetreet{O} + n% omga(r) 美元 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
MoCoGAN 分解运动和内容的视频生成
CreateAMind
18+阅读 · 2017年10月21日
Self-Healing First-Order Distributed Optimization
Arxiv
0+阅读 · 2021年4月5日
Arxiv
45+阅读 · 2019年12月20日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
【TED】什么让我们生病
英语演讲视频每日一推
7+阅读 · 2019年1月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
MoCoGAN 分解运动和内容的视频生成
CreateAMind
18+阅读 · 2017年10月21日
Top
微信扫码咨询专知VIP会员