Discrete optimal transport: complexity, geometry and applications - Université Grenoble Alpes
Article Dans Une Revue Discrete and Computational Geometry Année : 2016

Discrete optimal transport: complexity, geometry and applications

Quentin Mérigot

Résumé

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.
Fichier principal
Vignette du fichier
lsmatching.pdf (742.35 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00980195 , version 1 (12-05-2014)

Identifiants

Citer

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

Altmetric

Partager

More