论文标题
充血集团中最短的路径呈指数级更快
Exponentially Faster Shortest Paths in the Congested Clique
论文作者
论文摘要
我们提出了改进的确定性算法，用于近似分布式计算的拥塞集合模型中的最短路径。我们获得了$ poly（\ log \ log n）$ - 在未加权的$ n $ vertex图中，用于以下问题的圆形算法： - $（1+ε）$ - 从$ o（\ sqrt {n}）$来源的多源最短路径（MSSP）的近似。 - $（2+ε）$ - 所有对最短路径的近似（APSP）。 - $（1+ε，β）$ - apsp的近似，其中$β= o（\ frac {\ log \ log \ log n}ε）^{\ log \ log \ log n} $。 这些界限在[Censor-Hillel等人，PODC19]引起的最先进的多层次界面上呈指数增长。它还为APSP问题提供了第一个几乎加节的界限。我们的方法是基于根据某个距离阈值$ t = o（\fracβε）$区分短距离和长距离的，其中$β= o（\ frac {\ log \ log \ log \ log n}ε）^{\ log log \ log \ log n} $。通过设计一种用于计算稀疏$（1+ε，β）$仿真器的新算法来完成长距离的处理，以$ o（n \ log \ log n）$ edges。对于短距离，我们为[Cencor-Hillel等人，PODC19]的距离工具套件提供距离敏感的变体。通过利用此工具套件应仅应用于半径$ t $的本地球的事实，它们的圆形复杂性可以从$ poly（\ log n）$改善到$ poly（\ log t）$。 最后，我们针对这些问题的确定性解决方案是基于击中设定问题的新型变体的衍生化方案，这可能是独立的。
We present improved deterministic algorithms for approximating shortest paths in the Congested Clique model of distributed computing. We obtain $poly(\log\log n)$-round algorithms for the following problems in unweighted undirected $n$-vertex graphs: -- $(1+ε)$-approximation of multi-source shortest paths (MSSP) from $O(\sqrt{n})$ sources. -- $(2+ε)$-approximation of all pairs shortest paths (APSP). -- $(1+ε,β)$-approximation of APSP where $β=O(\frac{\log\log n}ε)^{\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(\fracβε)$ where $β=O(\frac{\log\log n}ε)^{\log\log n}$. Handling the long distances is done by devising a new algorithm for computing sparse $(1+ε,β)$ emulator with $O(n\log\log n)$ 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(\log n)$ 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.
