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

Joint work with Jiashuai Lu

Journal of Computational Geometry, 13(1), 204–225

pdf

Abstract

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 + \varepsilon)\)-approximation to the optimal transportation map in \(n~\varepsilon^{-O(d)} \log^{O(d)} 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.