Datensatz

Zusammenfassung

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.