# Faster Algorithms for the Geometric Transportation Problem

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2019.

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

- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)

## Abstract (arXiv)

Let R and B be two point sets in ℝd, with |R|+ |B| = n and where d is a constant. Next, let λ : R cup B → mathbbN such that sumr ∈ R  λ(r) = sumb ∈ B λ(b) be demand functions over R and B. Let |·| be a suitable distance function such as the Lp distance. The transportation problem asks to find a map τ : R × B → mathbbN such that sumb ∈ Bτ(r,b) = λ(r), sumr ∈ Rτ(r,b) = λ(b), and sumr ∈ R, b ∈ B τ(r,b) |r-b| is minimized. We present three new results for the transportation problem when |r-b| is any Lp metric: - For any constant varepsilon > 0, an O(n1+varepsilon) expected time randomized algorithm that returns a transportation map with expected cost O(log2(1/varepsilon)) times the optimal cost. - For any varepsilon > 0, a (1+varepsilon)-approximation in O(n3/2varepsilon-d operatornamepolylog(U) operatornamepolylog(n)) time, where U = maxp∈ Rcup B λ(p). - An exact strongly polynomial O(n2 operatornamepolylogn) time algorithm, for d = 2.