On the structure of optimal transportation plans between discrete measures

DOI10.1007/S00245-022-09861-4zbMATH Open1497.49055arXiv2104.13106OpenAlexW3158585035MaRDI QIDQ2674441FDOQ2674441

Authors: Gennaro Auricchio, Marco Veneroni 

Publication date: 12 September 2022

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: In this paper, we prove a structure theorem for discrete optimal transportation plans. We show that, given any pair of discrete probability measures and a cost function, there exists an optimal transportation plan that can be expressed as the sum of two deterministic plans. As an application, we estimate the infinity-Wasserstein distance between two discrete probability measures $mu$ and $u$ with the $p$-Wasserstein distance, times a constant depending on $mu$, $u$, and the fixed cost function.

Full work available at URL: https://arxiv.org/abs/2104.13106

Recommendations

• \({\mathcal{W}}_\infty \)-transport with discrete target as a combinatorial matching problem
• Full characterization of optimal transport plans for concave costs
• Discrete optimal transport: complexity, geometry and applications
• Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
• Optimal measure transportation with respect to non-traditional costs

zbMATH Keywords

discrete optimal transportWasserstein distanceuniform estimatesMonge-Kantorovich problemstructure of solutions

Mathematics Subject Classification ID

Optimal transportation (49Q22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Functional inequalities, including subadditivity, convexity, etc. (39B62)

Cites Work

• The earth mover's distance as a metric for image retrieval
• Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
• Vlasov equations
• A characterization of random variables with minimum \(L^ 2\)-distance
• The geometry of optimal transportation
• On the monotonicity of optimal transportation plans
• An inequality for certain functional of multidimensional probability distributions
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• On mass transportation
• Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs
• Polar factorization and monotone rearrangement of vector‐valued functions
• An inequality for a functional of probability distributions and its application to Kac's one-dimensional model of a Maxwellian gas
• Probabilistic treatment of the Boltzmann equation of Maxwellian molecules
• Caractérisation d'une solution optimale au problème de Monge-Kantorovitch
• A new $L^\infty$ estimate in optimal mass transport
• Gradient flows in metric spaces and in the space of probability measures
• Existence, Uniqueness, and Regularity of Optimal Transport Maps
• Optimal Transport
• On the regularity of solutions of optimal transportation problems
• Linear Programming
• On minimum Kantorovich distance estimators
• Asymptotic Properties and Robustness of Minimum Dissimilarity Estimators of Location-scale Parameters
• On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows

Cited In (6)

• 3/4-discrete optimal transport
• Quantitative stability and error estimates for optimal transport plans
• \({\mathcal{W}}_\infty \)-transport with discrete target as a combinatorial matching problem
• On the Pythagorean Structure of the Optimal Transport for Separable Cost Functions
• On discontinuity of planar optimal transport maps
• On the geometry of geodesics in discrete optimal transport

Uses Software

• EMD
• Wasserstein GAN

This page was built for publication: On the structure of optimal transportation plans between discrete measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674441)