  Let $R$ and $B$ be two point sets in $\mathbb{R}^d$, with $|R|+ |B| = 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 $\|\cdot\|$ 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}$ such that $\sum_{b \in B}\tau(r,b) = \lambda(r)$,
$\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 $\|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} \lambda(p)$.
  - An exact strongly polynomial $O(n^2 \operatorname{polylog}n)$ time
algorithm, for $d = 2$.
