  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 $\varepsilon > 0$. In $O(\varepsilon^{-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
+ \varepsilon)$ 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 $\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.
