Abstract

We present a method for solving the transshipment problem—also known as uncapacitated minimum cost flow—up to a multiplicative error of 1 + ε in undirected graphs with non-negative edge weights using a tailored gradient descent algorithm. Using O~(·) to hide polylogarithmic factors in n (the number of nodes in the graph), our gradient descent algorithm takes O~(ε^{−2}) iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of polylog n. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior work by obtaining the following results:

1. Broadcast CONGEST model: (1 + ε)-approximate SSSP using O~(( n + D)ε^{−3} ) rounds, where D is the (hop) diameter of the network.
2. Broadcast congested clique model: (1 + ε)-approximate transshipment and SSSP using O~(ε^{−2} ) rounds.
3. Multipass streaming model: (1 + ε)-approximate transshipment and SSSP using O~(n) space and O~(ε^{−2}) 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 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.

Bio

Andreas Karrenbauer is a Senior Researcher in the Algorithms and Complexity Department of the Max Planck Institute for Informatics in Saarbrücken, Germany. His research interests are in in the area of mathematical optimization. He obtained his PhD from Saarland University, Germany, in 2007. He worked as a Postdoc at EPFL before moving to the University of Konstanz in 2010 to become a Research Fellow and a Research Group Leader. Since 2013, he coordinates the research area Combinatorial Optimization at MPII.