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

arXiv: https://arxiv.org/abs/2508.06774 · HTML: https://mlsanity.com/paper/2508.06774/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 9 Aug 2025.

## Builds on (most cited first, 17 of 17)

- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry](https://mlsanity.com/paper/1709.05282/) (2017)
- [Parallel Algorithms for Geometric Graph Problems](https://mlsanity.com/paper/1401.0042/) (2013)
- [New Streaming Algorithms for High Dimensional EMD and MST](https://mlsanity.com/paper/2111.03528/) (2021)
- [Nearly Maximum Flows in Nearly Linear Time](https://mlsanity.com/paper/1304.2077/) (2013)
- [Polynomial Representations of Threshold Functions and Algorithmic Applications](https://mlsanity.com/paper/1608.04355/) (2016)
- [Faster Algorithms for the Geometric Transportation Problem](https://mlsanity.com/paper/1903.08263/) (2019)
- [Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators](https://mlsanity.com/paper/1911.01956/) (2019)
- [Preconditioning for the Geometric Transportation Problem](https://mlsanity.com/paper/1902.08384/) (2019)
- [Faster Parallel Algorithm for Approximate Shortest Path](https://mlsanity.com/paper/1911.01626/) (2019)
- [Better Sum Estimation via Weighted Sampling](https://mlsanity.com/paper/2110.14948/) (2021)
- [A Simple Boosting Framework for Transshipment](https://mlsanity.com/paper/2110.11723/) (2021)
- [Deterministic, Near-Linear varepsilon-Approximation Algorithm for Geometric Bipartite Matching](https://mlsanity.com/paper/2204.03875/) (2022)
- [Fast Algorithms for a New Relaxation of Optimal Transport](https://mlsanity.com/paper/2307.10042/) (2023)
- [Approximate Earth Mover's Distance in Truly-Subquadratic Time](https://mlsanity.com/paper/2310.19514/) (2023)

## Abstract (arXiv)

We give a reduction from (1+varepsilon)-approximate Earth Mover's Distance (EMD) to (1+varepsilon)-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 subseteq (mathbb Rd,ℓp), 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 minx ∈ X, y∈ Y ||x-y||p. Our contribution is twofold: we show that if a (1+varepsilon)-approximate CP can be computed in time n2-φ, then a 1+O(varepsilon) approximation to EMD can be computed in time n2-Omega(φ); plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a (1+varepsilon)-approximation algorithm for EMD running in time n^2-tildeOmega(varepsilon1/3) for high-dimensional point sets, which improves over the prior fastest running time of n2-Omega(varepsilon2) [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.