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

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 \mathbb{R}$. The goal is to find a transportation map, a non-negative assignment $\tau :P\times P\to {\mathbb{R}}_{\ge 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 $n{\epsilon }^{-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.

19 pages, accepted to Journal of Computational Geometry, 2022