4.5 Article

Exponentially Faster Shortest Paths in the Congested Clique

期刊

JOURNAL OF THE ACM
卷 69, 期 4, 页码 -

出版社

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3527213

关键词

Shortest paths; congested clique; near-additive emulator

资金

  1. Israel Science Foundation [1696/14, 2084/18]
  2. European Union [755839]
  3. Minerva grant [713238]

向作者/读者索取更多资源

We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. Our algorithms achieve polynomial time complexity and exponentially improve the previous bounds for multi-source shortest paths, all pairs shortest paths, and approximate shortest paths problems. Our approach distinguishes between short and long distances and provides separate solutions for each category. Additionally, our solutions are based on a derandomization scheme of a novel variant of the hitting set problem.
We present improved deterministic algorithms for approximating shortest paths in the Congested Cliqe model of distributed computing. We obtain poly(log logn)-round algorithms for the following problems in unweighted undirected n-vertex graphs: (1 + epsilon)-approximation of multi-source shortest paths (MSSP) from O(root n) sources. (2 + epsilon)-approximation of all pairs shortest paths (APSP). (1 + epsilon, beta)-approximation of APSP where beta = O(log log n/epsilon)log log n. These bounds improve exponentially over the state-of-the-art poly-logarithmic bounds due to [Censor-Hillel et al., PODC19]. It also provides the first nearly-additive bounds for the APSP problem in sub-polynomial time. Our approach is based on distinguishing between short and long distances based on some distance threshold t = O(beta/epsilon) where beta = O(log log n/epsilon) log log n. Handling the long distances is done by devising a new algorithm for computing a sparse (1 + epsilon, beta) emulator with O(n log logn) edges. For the short distances, we provide distance-sensitive variants for the distance tool-kit of [Censor-Hillel et al., PODC19]. By exploiting the fact that this tool-kit should be applied only on local balls of radius t, their round complexities get improved from poly(logn) to poly(log t). Finally, our deterministic solutions for these problems are based on a derandomization scheme of a novel variant of the hitting set problem, which might be of independent interest.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据