  In the geometric transportation problem, we are given a collection of points
$P$ in $d$-dimensional Euclidean space, and each point is given a supply of
$\mu(p)$ units of mass, where $\mu(p)$ could be a positive or a negative
integer, and the total sum of the supplies is $0$. The goal is to find a flow
(called a transportation map) that transports $\mu(p)$ units from any point $p$
with $\mu(p) > 0$, and transports $-\mu(p)$ units into any point $p$ with
$\mu(p) < 0$. Moreover, the flow should minimize the total distance traveled by
the transported mass. The optimal value is known as the transportation cost, or
the Earth Mover's Distance (from the points with positive supply to those with
negative supply). This problem has been widely studied in many fields of
computer science: from theoretical work in computational geometry, to
applications in computer vision, graphics, and machine learning.
  In this work we study approximation algorithms for the geometric
transportation problem. We give an algorithm which, for any fixed dimension
$d$, finds a $(1+\varepsilon)$-approximate transportation map in time
nearly-linear in $n$, and polynomial in $\varepsilon^{-1}$ and in the logarithm
of the total supply. This is the first approximation scheme for the problem
whose running time depends on $n$ as $n\cdot \mathrm{polylog}(n)$. Our
techniques combine the generalized preconditioning framework of Sherman, which
is grounded in continuous optimization, with simple geometric arguments to
first reduce the problem to a minimum cost flow problem on a sparse graph, and
then to design a good preconditioner for this latter problem.
