Skip to Main content Skip to Navigation
Journal articles

Discrete optimal transport: complexity, geometry and applications

Abstract : 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.
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Edouard Oudet Connect in order to contact the contributor
Submitted on : Monday, May 12, 2014 - 1:04:39 PM
Last modification on : Friday, November 5, 2021 - 3:20:19 PM
Long-term archiving on: : Tuesday, August 12, 2014 - 10:40:34 AM


Files produced by the author(s)




Quentin Mérigot, Edouard Oudet. Discrete optimal transport: complexity, geometry and applications. Discrete and Computational Geometry, Springer Verlag, 2016, 55 (2), pp.263-283. ⟨10.1007/s00454-016-9757-7⟩. ⟨hal-00980195⟩



Les métriques sont temporairement indisponibles