Lune

FOCS2025Top-tier venue

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

Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten

Abstract

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⊂(Rd,ℓp)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 ℓpdistance. 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 (1 + ε)-approximate CP can be computed in time n2−ϕ, then a 1 + O(ε) approximation to EMD can be computed in time n2−Ω(ϕ).• Plugging in the fastest known algorithm for CP [5], we obtain a (1 + ε)-approximation algorithm for EMD running in time n2−Ω~(ε1/3){n^{2 - \tilde \Omega \left( {{\varepsilon ^{1/3}}} \right)}} for high-dimensional point sets, which improves over the prior fastest running time of n2−Ω(ε2){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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Faster parallel algorithm for approximate shortest path cites Parallel approximate undirected shortest paths via low hop emulators
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor IndexingTobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren et al.KDD 2026 · 2 citations
  2. A Scalable Constant-Factor Approximation Algorithm for Wp Optimal TransportPankaj K. Agarwal, Oliver Chubet, Sharath Raghvendra, Keegan YaoICLR 2026

Builds on8

  1. Maximum Flow and Minimum-Cost Flow in Almost-Linear TimeLi Chen, Rasmus Kyng, Yang P. Liu, Richard Peng et al.FOCS 2022 · 135 citations
  2. Parallel approximate undirected shortest paths via low hop emulatorsAlexandr Andoni, Clifford Stein, Peilin ZhongSTOC 2020 · 50 citations
  3. Faster parallel algorithm for approximate shortest pathJason LiSTOC 2020 · 48 citations
  4. New streaming algorithms for high dimensional EMD and MSTXi Chen, Rajesh Jayaram, Amit Levi, Erik WaingartenSTOC 2022 · 11 citations
  5. Better Sum Estimation via Weighted SamplingLorenzo Beretta, Jakub TetekSODA 2022 · 7 citations

Related papers

  1. Approximate Earth Mover's Distance in Truly-Subquadratic TimeLorenzo Beretta, Aviad RubinsteinSTOC 2024 · 3 citations
  2. Near-Linear Time Algorithm for the Chamfer DistanceAinesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal et al.NeurIPS 2023 · 9 citations
  3. A Robust Exact Algorithm for the Euclidean Bipartite Matching ProblemAkshaykumar Gattani, Sharath Raghvendra, Pouyan ShirzadianNeurIPS 2023 · 6 citations
  4. Tree Embedding in High Dimensions: Dynamic and Massively ParallelGramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong et al.SODA 2026
  5. Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with ApplicationsAlexandr Andoni, Hengjie ZhangFOCS 2023 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines