论文标题
加权图和分布式和平行应用的确定性低直径分解
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
论文作者
论文摘要
本文介绍了加权图的新的确定性和分布的低直径分解算法。特别是，我们表明，如果一个人可以在并行或分布式设置中有效计算近似距离，则还可以有效地计算低直径分解。因此，这意味着使用近似距离计算数量的多组数量来解决许多基于距离的问题的解决方案。 我们的低直径分解概括并扩展了从[Rozhoň，Ghaffari STOC 2020]开始的工作线，并以非常独立的方式加权图。此外，我们的聚类结果具有其他有用的属性，包括强直径保证，分离属性，将群集中心限制为指定的终端等等。应用程序包括： - 对于跨越跨树木（LSST）的第一个接近线性工作和多毛的深度随机和确定性并联算法，具有多毛的伸展。以前，最佳的并行LSST算法所需的$ M \ CDOT N^{O（1）} $ WORK和$ n^{o（1）} $深度，并且本质上是随机的。众所周知，尚无具有真正次级工作和亚线性深度的确定性LSST算法。 - 用于计算$ \ ell_1 $ - 将$ \ ell_1 $的确定性算法确定性算法的第一个近线性工作，并将其插入二维尺寸空间中，并带有多组矩阵失真。 $ \ ell_1 $ embeddings的最佳先前确定性算法要么需要大型多项式工作，要么固有地是顺序的。 即使我们将技术应用于未加权图中用强直径$ o（\ log^2 n）$计算球扣的经典问题，我们的新聚类算法仍然会导致圆形复杂性从$ o（\ log log^{10} n）$ rounds $ rounds $ rounds [chang，ghaffari podc 21]
This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approximate distances in a parallel or a distributed setting, one can also efficiently compute low-diameter decompositions. This consequently implies solutions to many fundamental distance based problems using a polylogarithmic number of approximate distance computations. Our low-diameter decomposition generalizes and extends the line of work starting from [Rozhoň, Ghaffari STOC 2020] to weighted graphs in a very model-independent manner. Moreover, our clustering results have additional useful properties, including strong-diameter guarantees, separation properties, restricting cluster centers to specified terminals, and more. Applications include: -- The first near-linear work and polylogarithmic depth randomized and deterministic parallel algorithm for low-stretch spanning trees (LSST) with polylogarithmic stretch. Previously, the best parallel LSST algorithm required $m \cdot n^{o(1)}$ work and $n^{o(1)}$ depth and was inherently randomized. No deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth was known. -- The first near-linear work and polylogarithmic depth deterministic algorithm for computing an $\ell_1$-embedding into polylogarithmic dimensional space with polylogarithmic distortion. The best prior deterministic algorithms for $\ell_1$-embeddings either require large polynomial work or are inherently sequential. Even when we apply our techniques to the classical problem of computing a ball-carving with strong-diameter $O(\log^2 n)$ in an unweighted graph, our new clustering algorithm still leads to an improvement in round complexity from $O(\log^{10} n)$ rounds [Chang, Ghaffari PODC 21] to $O(\log^{4} n)$.
