# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (public)

1607.05127v2

(Preprint), 809KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Becker, R., Karrenbauer, A., Krinninger, S., & Lenzen, C. (2016). Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. Retrieved from http://arxiv.org/abs/1607.05127.

Cite as: http://hdl.handle.net/11858/00-001M-0000-002B-8419-1

##### 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.