# Optimal transport: discretization and algorithms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2020.

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

- [Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections](https://mlsanity.com/paper/2107.01718/) (2021)
- [A Survey on Optimal Transport for Machine Learning: Theory and Applications](https://mlsanity.com/paper/2106.01963/) (2021)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Deep Learning for Mean Field Optimal Transport](https://mlsanity.com/paper/2302.14739/) (2023)
- [New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning](https://mlsanity.com/paper/2207.09588/) (2022)
- [Optimal Transport Features for Morphometric Population Analysis](https://mlsanity.com/paper/2208.05891/) (2022)
- [Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems](https://mlsanity.com/paper/2607.09139/) (2026)

## Abstract (arXiv)

This chapter describes techniques for the numerical resolution of optimal transport problems. We will consider several discretizations of these problems, and we will put a strong focus on the mathematical analysis of the algorithms to solve the discretized problems. We will describe in detail the following discretizations and corresponding algorithms: the assignment problem and Bertsekas auction's algorithm; the entropic regularization and Sinkhorn-Knopp's algorithm; semi-discrete optimal transport and Oliker-Prussner or damped Newton's algorithm, and finally semi-discrete entropic regularization. Our presentation highlights the similarity between these algorithms and their connection with the theory of Kantorovich duality.