# A Push-Relabel Based Additive Approximation for Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 20 references that are in the map.
- First posted on arXiv 7 Mar 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Wasserstein Discriminant Analysis](https://mlsanity.com/paper/1608.08063/) (2016)
- [A Graph Theoretic Additive Approximation of Optimal Transport](https://mlsanity.com/paper/1905.11830/) (2019)
- [A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings](https://mlsanity.com/paper/1903.10445/) (2019)
- [Exponentially Faster Massively Parallel Maximal Matching](https://mlsanity.com/paper/1901.03744/) (2019)

## Abstract (arXiv)

Optimal Transport is a popular distance metric for measuring similarity between distributions. Exact algorithms for computing Optimal Transport can be slow, which has motivated the development of approximate numerical solvers (e.g. Sinkhorn method). We introduce a new and very simple combinatorial approach to find an varepsilon-approximation of the OT distance. Our algorithm achieves a near-optimal execution time of O(n2/varepsilon2) for computing OT distance and, for the special case of the assignment problem, the execution time improves to O(n2/varepsilon). Our algorithm is based on the push-relabel framework for min-cost flow problems. Unlike the other combinatorial approach (Lahn, Mulchandani and Raghvendra, NeurIPS 2019) which does not have a fast parallel implementation, our algorithm has a parallel execution time of O(log n/varepsilon2). Interestingly, unlike the Sinkhorn algorithm, our method also readily provides a compact transport plan as well as a solution to an approximate version of the dual formulation of the OT problem, both of which have numerous applications in Machine Learning. For the assignment problem, we provide both a CPU implementation as well as an implementation that exploits GPU parallelism. Experiments suggest that our algorithm is faster than the Sinkhorn algorithm, both in terms of CPU and GPU implementations, especially while computing matchings with a high accuracy.