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.

  • 4
    $\begingroup$ 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. $\endgroup$
    – Gamow
    May 13 '20 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.