Name
Abstract | ||
|---|---|---|
We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $1 + epsilon$ in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes $O(epsilon^{-3} mathrm{polylog} n)$ iterations and in each iteration it needs to solve a variant of the transshipment problem up to a multiplicative error of $mathrm{polylog} n$. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. As a consequence, we improve prior work by obtaining the following results: (1) RAM model: $(1+epsilon)$-approximate transshipment in $tilde{O}(epsilon^{-3}(m + n^{1 + o(1)}))$ computational steps (leveraging a recent $O(m^{1+o(1)})$-step $O(1)$-approximation due to Sherman [2016]). (2) Multipass Streaming model: $(1 + epsilon)$-approximate transshipment and SSSP using $tilde{O}(n) $ space and $tilde{O}(epsilon^{-O(1)})$ passes. (3) Broadcast Congested Clique model: $(1 + epsilon)$-approximate transshipment and SSSP using $tilde{O}(epsilon^{-O(1)})$ rounds. (4) Broadcast Congest model: $(1 + epsilon)$-approximate SSSP using $tilde{O}(epsilon^{-O(1)}(sqrt{n} + D))$ rounds, where $ D $ is the (hop) diameter of the network. The previous fastest algorithms for the last three models above leverage sparse hop sets. We bypass the hop set computation; using a spanner is sufficient in 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. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Data Structures and Algorithms | Integer,Discrete mathematics,Combinatorics,Gradient descent,Multiplicative function,Logarithm,Spanner,Transshipment problem,Minimum-cost flow problem,Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1607.05127 | 6 |
PageRank | References | Authors |
0.58 | 1 | 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 |