Let $\mu$ & $\nu$ be a pair of discrete probability measures on $\mathbb{R}^d$ defined by
$$\mu = \frac{1}{n}\sum_{i=1}^n \delta_{x_i} \quad ;\quad \nu= \frac{1}{n}\sum_{i=1}^n \delta_{y_i}$$
where $x_i, y_i \in \mathbb{R}^d$. We can think of $\mu$ and $\nu$ as denoting two distributions of $n$ shipping crates on $\mathbb{R}^d$ where crates have equal mass and can be stacked on top of one another. I want to find an algorithm to compute the Wasserstein distance between $\mu$ and $\nu$. The Wasserstein distance is given by
$$ W_p(\mu,\nu) = \min_{\sigma \in S_n} \left\{ \frac{1}{n} \sum_{i=1}^n |x_i-y_{\sigma(i)} |^p \right\}. \hskip20pt (*)$$
I.e. The Wasserstein distance gives the minimum cost necessary to move all crates from distribution $\mu$ to distribution $\nu$, where the cost for moving a crate from $x$ to $y$ in this case is $\frac{1}{n}|x - y|^p$. See e.g. Villani - Topics in Optimal Transport Theory, page 5.
The minimizer clearly exists because $S_n$ is finite, but (at least naively) it seems to be difficult to compute in practice because $|S_n| = n!$. Looking online I find some hints that the problem might be solvable in polynomial time, but I become stooped in complicated general theory which does not immediately seem to apply to this problem. I am not familiar with either optimal transport theory or optimization. I am most interested in the case $p=1$, though the cases $p\in(1,\infty)$ are also of interest.
Can anyone provide either:
(i) An account of existing theory/algorithms for computing (*), ideally in the case $p=1$ but also possibly for general $p\in[1,\infty)$, or
(ii) Some clear references covering (i).
Many thanks! A.
