A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs

We describe a simple deterministic near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs with real edge weights, a problem also known as transshipment. Specifically, our algorithm takes as input a (connected) undirected graph $G=(V,E)$, vertex demands $b\in {\mathbb{R}}^V$ such that ${\sum }_{v\in V}b(v)=0$, positive edge costs $c\in {\mathbb{R}}_{>0}^E$, and a parameter $\epsilon >0$. In $O({\epsilon }^{-2}m{\log }^{O(1)}n)$ time, it returns a flow $f$ such that the net flow out of each vertex is equal to the vertex’s demand and the cost of the flow is within a $(1+\epsilon )$ factor of optimal. Our algorithm is combinatorial and has no running time dependency on the demands or edge costs. With the exception of a recent result presented at STOC 2022 for polynomially bounded edge weights, all almost- and near-linear time approximation schemes for transshipment relied on randomization to embed the problem instance into low-dimensional space. Our algorithm instead deterministically approximates the cost of routing decisions that would be made if the input were subject to a random tree embedding. To avoid computing the $\mathrm{\Omega }(n^2)$ vertex-vertex distances that an approximation of this kind suggests, we also take advantage of the clustering method used in the well-known Thorup-Zwick distance oracle.