Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

We give a reduction from $(1+\epsilon )$-approximate Earth Mover’s Distance (EMD) to $(1+\epsilon )$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1,2]$ and two sets of $n$ points $X,Y\subseteq ({\mathbb{R}}^d,{\mathrm{\ell }}_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their ${\mathrm{\ell }}_p$ distance. Further, CP is the basic problem of finding a pair of points realizing ${\min }_{x\in X,y\in Y}\mathrm{\mid }\mathrm{\mid }x-y\mathrm{\mid }{\mathrm{\mid }}_p$. Our contribution is twofold: we show that if a $(1+\epsilon )$-approximate CP can be computed in time $n^{2-\phi }$, then a $1+O(\epsilon )$ approximation to EMD can be computed in time $n^{2-\mathrm{\Omega }(\phi )}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS’16], we obtain a $(1+\epsilon )$-approximation algorithm for EMD running in time $n^{2-\tilde{\mathrm{\Omega }}({\epsilon }^{1\mathrm{/}3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-\mathrm{\Omega }({\epsilon }^2)}$ [Andoni, Zhang FOCS’23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.