A deterministic near-linear time approximation scheme for geometric transportation

Given a set of points $P=(P^{+}\bigsqcup P^{-})\subset {\mathbb{R}}^d$ for some constant $d$ and a supply function $\mu :P\to \mathbb{R}$ such that $\mu (p)>0\mathrm{\forall }p\in P^{+}$, $\mu (p)<0\mathrm{\forall }p\in P^{-}$, and ${\sum }_{p\in P}\mu (p)=0$, the geometric transportation problem asks one to find a transportation map $\tau :P^{+}\times P^{-}\to {\mathbb{R}}_{\ge 0}$ such that ${\sum }_{q\in P^{-}}\tau (p,q)=\mu (p)\mathrm{\forall }p\in P^{+}$, ${\sum }_{p\in P^{+}}\tau (p,q)=-\mu (q)\mathrm{\forall }q\in P^{-}$, and the weighted sum of Euclidean distances for the pairs ${\sum }_{(p,q)\in P^{+}\times P^{-}}\tau (p,q)\cdot \mathrm{\mid }\mathrm{\mid }q-p\mathrm{\mid }{\mathrm{\mid }}_2$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $(1+\epsilon )$ factor of optimal. More precisely, our algorithm runs in $O(n{\epsilon }^{-(d+2)}{\log }^{5}n\log \log n)$ time for any constant $\epsilon >0$. Surprisingly, our result is not only a generalization of a bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $(1+\epsilon )$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1+\epsilon )$-approximate deterministic algorithm for geometric bipartite matching and the first $(1+\epsilon )$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $d$ in the exponent of the running time’s polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O({\epsilon }^{-2}m{\log }^{O(1)}n)$ time $(1+\epsilon )$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.