# Approximate Earth Mover's Distance in Truly-Subquadratic Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2023.

## Built on by (most cited first, 1 of 1)

- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)

## Abstract (arXiv)

We design an additive approximation scheme for estimating the cost of the min-weight bipartite matching problem: given a bipartite graph with non-negative edge costs and varepsilon > 0, our algorithm estimates the cost of matching all but O(varepsilon)-fraction of the vertices in truly subquadratic time O(n2-δ(varepsilon)). Our algorithm has a natural interpretation for computing the Earth Mover's Distance (EMD), up to a varepsilon-additive approximation. Notably, we make no assumptions about the underlying metric (more generally, the costs do not have to satisfy triangle inequality). Note that compared to the size of the instance (an arbitrary n × n cost matrix), our algorithm runs in em sublinear time. Our algorithm can approximate a slightly more general problem: max-cardinality bipartite matching with a knapsack constraint, where the goal is to maximize the number of vertices that can be matched up to a total cost B.