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

Manuscript, 2024

pdf

Abstract

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 limit the available routing decisions using distances explicitly stored in the well-known Thorup-Zwick distance oracle.