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

Ruben Becker, Sebastian Forster, Andreas Karrenbauer +1

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 w…