  Given a set of points $P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$ for some
constant $d$ and a supply function $\mu:P\to \mathbb{R}$ such that $\mu(p) >
0~\forall p \in P^+$, $\mu(p) < 0~\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)~\forall p \in P^+$, $\sum_{p\in
P^+}{\tau(p, q)} = -\mu(q)~ \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
||q-p||_2$ is minimized. We present the first deterministic algorithm that
computes, in near-linear time, a transportation map whose cost is within a $(1
+ \varepsilon)$ factor of optimal. More precisely, our algorithm runs in
$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$ time for any constant
$\varepsilon > 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 + \varepsilon)$-approximation
algorithms, randomized or deterministic, even for geometric bipartite matching.
In particular, we give the first $(1 + \varepsilon)$-approximate deterministic
algorithm for geometric bipartite matching and the first $(1 +
\varepsilon)$-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(\varepsilon^{-2} m \log^{O(1)} n)$ time $(1 +
\varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow
(transshipment) problem in undirected graphs with arbitrary real edge costs.
