hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
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.
