Faster Algorithms for the Geometric Transportation Problem

Let $R$ and $B$ be two point sets in $\mathbb{R}^d$, with $|R|+ |B| = n$ and where $d$ is a constant. Next, let $λ: R \cup B \to \mathbb{N}$ such that $\sum_{r \in R } λ(r) = \sum_{b \in B} λ(b)$ be demand functions over $R$ and $B$. Let $\|\cdot\|$ be a suitable distance function such as the $L_p$ distance. The transportation problem asks to find a map $τ: R \times B \to \mathbb{N}$ such that $\sum_{b \in B}τ(r,b) = λ(r)$, $\sum_{r \in R}τ(r,b) = λ(b)$, and $\sum_{r \in R, b \in B} τ(r,b) \|r-b\|$ is minimized. We present three new results for the transportation problem when $\|r-b\|$ is any $L_p$ metric: - For any constant $\varepsilon > 0$, an $O(n^{1+\varepsilon})$ expected time randomized algorithm that returns a transportation map with expected cost $O(\log^2(1/\varepsilon))$ times the optimal cost. - For any $\varepsilon > 0$, a $(1+\varepsilon)$-approximation in $O(n^{3/2}\varepsilon^{-d} \operatorname{polylog}(U) \operatorname{polylog}(n))$ time, where $U = \max_{p\in R\cup B} λ(p)$. - An exact strongly polynomial $O(n^2 \operatorname{polylog}n)$ time algorithm, for $d = 2$.