An $\tilde{O}(n^{5/4})$ Time $\epsilon$-Approximation Algorithm for RMS Matching in a Plane

Nathaniel Lahn, Sharath Raghvendra

The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions that has exciting applications in machine learning. For discrete di…