Discrete optimal transport : complexity, geometry and applications Article - Mars 2016

Quentin Mérigot, Edouard Oudet

Quentin Mérigot, Edouard Oudet, « Discrete optimal transport : complexity, geometry and applications  », Discrete and Computational Geometry, mars 2016, pp. 263–283. ISSN 0179-5376


In this article, we introduce a new algorithm for solving discrete optimal transport based on iterative resolutions of local versions of the dual linear program. We show a quantitative link between the complexity of this algorithm and the geometry of the underlying measures in the quadratic Euclidean case. This discrete method is then applied to investigate to wo optimal transport problems with geometric flavor : the regularity of optimal transport plan on oblate ellipsoids, and Alexandrov’s problem of reconstructing a convex set from its Gaussian measure.

Voir la notice complète sur HAL