A near-linear time approximation scheme for geometric transportation with arbitrary supplies and spread

Abstract

$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\poly}{poly}\DeclareMathOperator{\polylog}{polylog}$The geometric transportation problem takes as input a set of points \(P\) in \(d\)-dimensional Euclidean space and a supply function \(\mu : P \to \R\).
The goal is to find a transportation map, a non-negative assignment \(\tau : P \times P \to \R_{\geq 0}\) to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., \(\sum_{r \in P} \tau(q, r) - \sum_{p \in P} \tau(p, q) = \mu(q)\) for all points \(q \in P\). The goal is to minimize the weighted sum of Euclidean distances for the pairs, \(\sum_{(p, q) \in P \times P} \tau(p, q) \cdot ||q - p||_2\).

We describe the first algorithm for this problem that returns, with high probability, a \((1 + \epsilon)\)-approximation to the optimal transportation map in \(O(n \poly(1 / \epsilon) \polylog{n})\) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of \(P\) and the magnitude of its real-valued supplies.