Name
Title | ||
|---|---|---|
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. |
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2017 | DISC | Integer,Discrete mathematics,Gradient descent,Combinatorics,Clique,Multiplicative function,Logarithm,Spanner,Transshipment problem,Minimum-cost flow problem,Mathematics |
DocType | Citations | PageRank |
Conference | 5 | 0.40 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruben Becker | 1 | 31 | 5.27 |
| Andreas Karrenbauer | 2 | 133 | 20.21 |
| Sebastian Krinninger | 3 | 227 | 15.42 |
| Christoph Lenzen | 4 | 584 | 40.61 |