Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
复制标题
分布式和流式模型中的近最优近似最短路径和转运
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Lenzen
中科院分区：
文献类型：
--
作者：
R. Becker;Andreas Karrenbauer;Sebastian Krinninger;C. Lenzen
我们提出了一种利用定制的梯度下降算法来解决边权非负整数无向图中乘性误差为(1+epsilon)的最短转运问题的方法。我们的梯度下降算法需要epsilon^(-3)PolyLog(N)次迭代，在每一次迭代中，它需要求解转运问题的一个实例，直到PolyLog(N)的乘性误差，其中n是节点数。特别是，这允许我们通过在对数拉伸的稀疏扳手上计算解来执行单次迭代。通过仔细的白盒分析，我们可以进一步将该方法扩展到寻找单源最短路径问题的近似解。因此，我们通过获得以下结果来改进先前的工作：
(1)广播拥塞模型：(1+epsilon)-用~O((Sqrt(N)+D)epsilon^(-O(1)轮数逼近SSSP，其中D是网络的(跳数)直径。
(2)广播拥挤团模型：(1+epsilon)-近似最短转运和使用~O(epsilon^(-O(1)轮次的SSSP。
(3)多通道流模型：(1+epsilon)--近似最短转运和使用~O(N)空间和~O(epsilon^(-O(1)通道的SSSP。
这些模型以前最快的SSSP算法利用稀疏跳集。我们绕过了跳集构造；用我们的方法计算扳手就足够了。上面的界限假设非负整数边权重在n中多项式有界；对于一般的非负权重，运行时间以非零权重之间的最大比率的对数进行缩放。在沿相反方向遍历边的成本不对称的情况下，运行时间按所有边的两个方向的成本之间的最大比率进行调整。
We present a method for solving the shortest transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of (1 + epsilon) in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes epsilon^(-3) polylog(n) iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog(n), where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results:
(1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using ~O((sqrt(n) + D) epsilon^(-O(1))) rounds, where D is the (hop) diameter of the network.
(2) Broadcast congested clique model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(epsilon^(-O(1))) rounds.
(3) Multipass streaming model: (1 + epsilon)-approximate shortest transshipment and SSSP using ~O(n) space and ~O(epsilon^(-O(1))) passes.
The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth