FOCS Conference 2025 Conference Paper
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
- Lorenzo Beretta 0001
- Vincent Cohen-Addad
- Rajesh Jayaram
- Erik Waingarten
We give a reduction from (1 + ε)-approximate Earth Mover’s Distance (EMD) to (1 + ε)-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p ∈ [1], [2] and two sets of n points $X, Y \subset \left( {{\mathbb{R}^d}, {\ell _p}} \right)$, their EMD is the minimum cost of a perfect matching between X and Y, where the cost of matching two vectors is their ℓ p distance. Further, CP is the basic problem of finding a pair of points realizing min x∈X, y∈Y ║x − y║ p. Our contribution is twofold: • We show that if (1 + ε)-approximate CP can be computed in time n 2−ϕ, then a 1 + O(ε) approximation to EMD can be computed in time n 2−Ω(ϕ). • Plugging in the fastest known algorithm for CP [5], we obtain a (1 + ε)-approximation algorithm for EMD running in time ${n^{2 - \tilde \Omega \left( {{\varepsilon ^{1/3}}} \right)}}$ for high-dimensional point sets, which improves over the prior fastest running time of ${n^{2 - \Omega \left( {{\varepsilon ^2}} \right)}}$ [13]. 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.