A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
share
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 ∈ℝ^V such that ∑_v ∈ V b(v) = 0, positive edge costs c ∈ℝ_>0^E, and a parameter ε > 0. In O(ε^-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 + ε) 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 in two main ways: 1) to embed the problem instance into low-dimensional space and 2) to randomly pick target locations to send flow so nearby opposing demands can be satisfied. 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 Ω(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.
READ FULL TEXT