Low Diameter Graph Decompositions by Approximate Distance Computation
Low Diameter Graph Decompositions by Approximate Distance Computation
复制标题
通过近似距离计算进行小直径图分解
DOI：
10.4230/lipics.itcs.2020.50
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
C. Lenzen
中科院分区：
文献类型：
--
作者：
R. Becker;Y. Emek;C. Lenzen
在大规模计算的许多模型中，问题的分解是高效算法的关键。对于距离相关的图问题，通常至关重要的是，这样的分解导致小直径的簇，而边被分解切割的概率与边的长度成线性比例。有大量关于具有小边缘切割概率的低直径图分解的文献，所有现有技术都大量建立在单源最短路径（SSSP）计算上。不幸的是，在许多大规模计算的理论模型中，SSSP任务构成了复杂性瓶颈。因此，希望用近似值代替精确SSSP计算。然而，这提出了一个根本性的挑战，因为现有的这种分解的结构本质上依赖于三角形不等式的减法形式。本文通过开发一种称为模糊球生长的技术克服了这一障碍。通过将这种技术与米勒等人（SPAA 13）的一个巧妙的算法思想相结合，我们获得了一个具有小边缘切割概率的低直径分解的构造，该构造用（少量的）近似计算代替了精确的SSSP计算。我们的方法的效用是通过推导出有效的算法，工作在拥塞，PRAM和半流计算模型。作为一个应用，我们得到度量树嵌入算法的静脉Bartal（FOCS 96），其计算复杂性在这些模型中是最佳的多对数因子。我们的嵌入有额外的有用的属性，树可以被映射回原来的图，使每个边缘是“使用”只有O（log n）次，这是有兴趣的能力限制的问题，并模拟拥塞算法的树上的图形被嵌入。
In many models for large-scale computation, decomposition of the problem is key to efficient algorithms. For distance-related graph problems, it is often crucial that such a decomposition results in clusters of small diameter, while the probability that an edge is cut by the decomposition scales linearly with the length of the edge. There is a large body of literature on low diameter graph decomposition with small edge cutting probabilities, with all existing techniques heavily building on single source shortest paths (SSSP) computations. Unfortunately, in many theoretical models for large-scale computations, the SSSP task constitutes a complexity bottleneck. Therefore, it is desirable to replace exact SSSP computations with approximate ones. However this imposes a fundamental challenge since the existing constructions of such decompositions inherently rely on the subtractive form of the triangle inequality. The current paper overcomes this obstacle by developing a technique termed blurry ball growing. By combining this technique with a clever algorithmic idea of Miller et al. (SPAA 13), we obtain a construction of low diameter decompositions with small edge cutting probabilities which replaces exact SSSP computations by (a small number of) approximate ones. The utility of our approach is showcased by deriving efficient algorithms that work in the Congest, PRAM, and semi-streaming models of computation. As an application, we obtain metric tree embedding algorithms in the vein of Bartal (FOCS 96) whose computational complexities in these models are optimal up to polylogarithmic factors. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is "used" only O(log n) times, which is of interest for capacitated problems and simulating Congest algorithms on the tree into which the graph is embedded.
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth