# Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2023.

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

- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)
- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)

## Abstract (arXiv)

Given a d-dimensional continuous (resp. discrete) probability distribution μ and a discrete distribution nu, the semi-discrete (resp. discrete) Optimal Transport (OT) problem asks for computing a minimum-cost plan to transport mass from μ to nu; we assume n to be the size of the support of the discrete distributions, and we assume we have access to an oracle outputting the mass of μ inside a constant-complexity region in O(1) time. In this paper, we present three approximation algorithms for the OT problem. (i) Semi-discrete additive approximation: For any ε>0, we present an algorithm that computes a semi-discrete transport plan with ε-additive error in nO(d)logfracCmaxε time; here, Cmax is the diameter of the supports of μ and nu. (ii) Semi-discrete relative approximation: For any ε>0, we present an algorithm that computes a (1+ε)-approximate semi-discrete transport plan in nε-O(d)log(n)logO(d)(log n) time; here, we assume the ground distance is any Lp norm. (iii) Discrete relative approximation: For any ε>0, we present a Monte-Carlo (1+ε)-approximation algorithm that computes a transport plan under any Lp norm in nε-O(d)log(n)logO(d)(log n) time; here, we assume that the spread of the supports of μ and nu is polynomially bounded.