# Approximating optimal transport with linear programs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2018.

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

- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Improved Rate of First Order Algorithms for Entropic Optimal Transport](https://mlsanity.com/paper/2301.09675/) (2023)
- [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)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Graph Cuts with Arbitrary Size Constraints Through Optimal Transport](https://mlsanity.com/paper/2402.04732/) (2024)
- [Efficient Optimal Transport Algorithm by Accelerated Gradient descent](https://mlsanity.com/paper/2104.05802/) (2021)
- [A machine learning based algorithm selection method to solve the minimum cost flow problem](https://mlsanity.com/paper/2210.02195/) (2022)
- [Feature Shift Localization Network](https://mlsanity.com/paper/2506.09101/) (2025)

## Abstract (arXiv)

In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear programs, resulting in faster additive approximation algorithms for optimal transport.