Faster Algorithms for the Geometric Transportation Problem

Let $R$ and $B$ be two point sets in ${\mathbb{R}}^d$, with $\mathrm{\mid }R\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }=n$ and where $d$ is a constant. Next, let $\lambda :R\cup B\to \mathbb{N}$ such that ${\sum }_{r\in R}\lambda (r)={\sum }_{b\in B}\lambda (b)$ be demand functions over $R$ and $B$. Let $\mathrm{\parallel }\cdot \mathrm{\parallel }$ be a suitable distance function such as the $L_p$ distance. The transportation problem asks to find a map $\tau : R \times B \to $\mathbb{N}$$suchthat$\sum_{b \in B}\tau(r,b) = \lambda®$,$\sum_{r \in R}\tau(r,b) = \lambda(b)$,and$\sum_{r \in R, b \in B} \tau(r,b) |r-b|$ is minimized. We present three new results for the transportation problem when $\mathrm{\parallel }r-b\mathrm{\parallel }$ is any $L_p$ metric:

• For any constant $\epsilon >0$, an $O(n^{1+\epsilon })$ expected time randomized algorithm that returns a transportation map with expected cost $O({\log }^2(1\mathrm{/}\epsilon ))$ times the optimal cost.
• For any $\epsilon >0$, a $(1+\epsilon )$-approximation in $O(n^{3/2}\varepsilon^{-d} \operatorname{polylog}(U) \operatorname{polylog}(n))$time,where$U = \max_{p\in R\cup B} \lambda(p)$.
• An exact strongly polynomial $O(n^2\mathrm{polylog}n)$ time algorithm, for $d=2$.