# Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality

Let p and q by two categorical probability distributions over $$\{1,2,...,k\}$$. Given a set of costs $$c_{ij} \ge 0, i,j \in \{1,2,...,k\}$$ that satisfy the triangle inequality, that is $$c_{ij} \le c_{ik} + c_{kj}, i,j,k \in \{1,2,...,k\}$$, what is the complexity of the best known algorithm for computing the Earth Mover's Distance between p and q , EMD(p,q) ?

I found that the time complexity is in general $$O(n^3)$$ and some linear time approximations are known, but it is not clear to me if any improvement was achieved if the costs satisfy the triangle inequality.

• If you add the same constant $M$ to all costs $c_{ij}$, the structure and the optimal solution of the problem will not change. If $M$ is large enough, the costs will satisfy the triangle inequality. May 13 '20 at 15:34