# A Graph Theoretic Additive Approximation of Optimal Transport

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients](https://mlsanity.com/paper/2307.08507/) (2023)
- [A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions](https://mlsanity.com/paper/2405.03664/) (2024)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [A Survey on Algorithmic Developments in Optimal Transport Problem with Applications](https://mlsanity.com/paper/2501.06247/) (2025)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [A Push-Relabel Based Additive Approximation for Optimal Transport](https://mlsanity.com/paper/2203.03732/) (2022)
- [Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation](https://mlsanity.com/paper/2605.20122/) (2026)

## Abstract (arXiv)

Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly can be prohibitively expensive. Therefore, there has been significant effort towards the design of scalable approximation algorithms. Previous combinatorial results [Sharathkumar, Agarwal STOC '12, Agarwal, Sharathkumar STOC '14] have focused primarily on the design of near-linear time multiplicative approximation algorithms. There has also been an effort to design approximate solutions with additive errors [Cuturi NIPS '13, Altschuler etal NIPS '17, Dvurechensky etal, ICML '18, Quanrud, SOSA '19] within a time bound that is linear in the size of the cost matrix and polynomial in C/δ; here C is the largest value in the cost matrix and δ is the additive error. We present an adaptation of the classical graph algorithm of Gabow and Tarjan and provide a novel analysis of this algorithm that bounds its execution time by O(fracn2 Cδ+ fracnC2δ2). Our algorithm is extremely simple and executes, for an arbitrarily small constant varepsilon, only lfloor frac2C(1-varepsilon)δrfloor + 1 iterations, where each iteration consists only of a Dijkstra-type search followed by a depth-first search. We also provide empirical results that suggest our algorithm is competitive with respect to a sequential implementation of the Sinkhorn algorithm in execution time. Moreover, our algorithm quickly computes a solution for very small values of δ whereas Sinkhorn algorithm slows down due to numerical instability.