  In this work, we provide faster algorithms for approximating the optimal
transport distance, e.g. earth mover's distance, between two discrete
probability distributions $\mu, \nu \in \Delta^n$. Given a cost function $C :
[n] \times [n] \to \mathbb{R}_{\geq 0}$ where $C(i,j) \leq 1$ quantifies the
penalty of transporting a unit of mass from $i$ to $j$, we show how to compute
a coupling $X$ between $r$ and $c$ in time $\widetilde{O}\left(n^2 /\epsilon
\right)$ whose expected transportation cost is within an additive $\epsilon$ of
optimal. This improves upon the previously best known running time for this
problem of $\widetilde{O}\left(\text{min}\left\{ n^{9/4}/\epsilon,
n^2/\epsilon^2 \right\}\right)$.
  We achieve our results by providing reductions from optimal transport to
canonical optimization problems for which recent algorithmic efforts have
provided nearly-linear time algorithms. Leveraging nearly linear time
algorithms for solving packing linear programs and for solving the matrix
balancing problem, we obtain two separate proofs of our stated running time.
Further, one of our algorithms is easily parallelized and can be implemented
with depth $\widetilde{O}(1/\epsilon)$.
  Moreover, we show that further algorithmic improvements to our result would
be surprising in the sense that any improvement would yield an $o(n^{2.5})$
algorithm for \textit{maximum cardinality bipartite matching}, for which
currently the only known algorithms for achieving such a result are based on
fast-matrix multiplication.
