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

https://hal.univ-grenoble-alpes.fr/hal-00980195
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

File

lsmatching.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Les métriques sont temporairement indisponibles