# Fast Algorithms for a New Relaxation of Optimal Transport

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 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 introduce a new class of objectives for optimal transport computations of datasets in high-dimensional Euclidean spaces. The new objectives are parametrized by ρ ≥ 1, and provide a metric space Rρ(·, ·) for discrete probability distributions in ℝd. As ρ approaches 1, the metric approaches the Earth Mover's distance, but for ρ larger than (but close to) 1, admits significantly faster algorithms. Namely, for distributions μ and nu supported on n and m vectors in ℝd of norm at most r and any ε > 0, we give an algorithm which outputs an additive ε r-approximation to Rρ(μ, nu) in time (n+m) · poly((nm)(ρ-1)/ρ · 2ρ / (ρ-1) / ε).