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.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2016, 55 (2), pp.263-283. 〈10.1007/s00454-016-9757-7〉
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

http://hal.univ-grenoble-alpes.fr/hal-00980195
Contributeur : Edouard Oudet <>
Soumis le : lundi 12 mai 2014 - 13:04:39
Dernière modification le : lundi 9 avril 2018 - 12:22:50
Document(s) archivé(s) le : mardi 12 août 2014 - 10:40:34

Fichier

lsmatching.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

503

Téléchargements de fichiers

260