Comptes Rendus
Control theory
Intrinsic Sparsity of Kantorovich solutions
Comptes Rendus. Mathématique, Volume 360 (2022), pp. 1173-1175.

Let X,Y be two finite sets of points having #X=m and #Y=n points with μ=(1/m)(δ x 1 ++δ x m ) and ν=(1/n)(δ y 1 ++δ y n ) being the associated uniform probability measures. A result of Birkhoff implies that if m=n, then the Kantorovich problem has a solution which also solves the Monge problem: optimal transport can be realized with a bijection π:XY. This is impossible when mn. We observe that when mn, there exists a solution of the Kantorovich problem such that the mass of each point in X is moved to at most n/gcd(m,n) different points in Y and that, conversely, each point in Y receives mass from at most m/gcd(m,n) points in X.

Soient X et Y deux ensembles de points de cardinaux respectifs m et n ; et μ,ν les mesures de probabilité associées. Quand m=n, un résultat de Birkhoff assure que le problème de Kantorovitch a une solution qui résout aussi le problème de Monge  : une bijection réalise le transport optimal. Quand mn, nous montrons que le problème de Kantorovitch admet une solution telle que chaque point de X se déplace vers au plus n/pgcd(m,n) points de Y, et réciproquement, chaque point de Y reçoit de la masse d’au plus m/pgcd(m,n) points de X.

Received:
Accepted:
Published online:
DOI: 10.5802/crmath.392
Classification: 49Q20, 90C46
Bamdad Hosseini 1; Stefan Steinerberger 2

1 Department of Applied Mathematics, University of Washington, Seattle, USA
2 Department of Mathematics, University of Washington, Seattle, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{CRMATH_2022__360_G10_1173_0,
     author = {Bamdad Hosseini and Stefan Steinerberger},
     title = {Intrinsic {Sparsity} of {Kantorovich} solutions},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1173--1175},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {360},
     year = {2022},
     doi = {10.5802/crmath.392},
     language = {en},
}
TY  - JOUR
AU  - Bamdad Hosseini
AU  - Stefan Steinerberger
TI  - Intrinsic Sparsity of Kantorovich solutions
JO  - Comptes Rendus. Mathématique
PY  - 2022
SP  - 1173
EP  - 1175
VL  - 360
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.392
LA  - en
ID  - CRMATH_2022__360_G10_1173_0
ER  - 
%0 Journal Article
%A Bamdad Hosseini
%A Stefan Steinerberger
%T Intrinsic Sparsity of Kantorovich solutions
%J Comptes Rendus. Mathématique
%D 2022
%P 1173-1175
%V 360
%I Académie des sciences, Paris
%R 10.5802/crmath.392
%G en
%F CRMATH_2022__360_G10_1173_0
Bamdad Hosseini; Stefan Steinerberger. Intrinsic Sparsity of Kantorovich solutions. Comptes Rendus. Mathématique, Volume 360 (2022), pp. 1173-1175. doi : 10.5802/crmath.392. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.392/

[1] Garett Birkhoff Tres observaciones sobre el algebra lineal, Rev., Ser. A, Univ. Nac. Tucumán, Volume 5 (1946), pp. 147-151 | Zbl

[2] Haïm Brezis Remarks on the Monge-Kantorovich problem in the discrete setting, C. R. Math. Acad. Sci. Paris, Volume 356 (2018) no. 2, pp. 207-213 | DOI | MR | Zbl

[3] D. König Theorie der endlichen und unendlichen Graphen, Teubner-Archiv zur Mathematik, 6, Teubner, 1936 | Zbl

[4] Quentin Mérigot; Boris Thibert Optimal transport: discretization and algorithms, Geometric partial differential equations. Part 2 (Handbook of Numerical Analysis), Volume 22, Elsevier, 2021, pp. 133-212 | DOI | MR | Zbl

[5] John von Neumann A certain zero-sum two-person game equivalent to an optimal assignment problem, Contributions to the theory of games. Vol. 2 (Annals of Mathematics Studies), Volume 28, Princeton University Press, 1953, pp. 5-12 | MR | Zbl

[6] Gabriel Peyré; Marco Cuturi Computational optimal transport: With applications to data science, Found. Trends Mach. Learn., Volume 11 (2018) no. 5-6, pp. 355-407 | DOI | Zbl

Cited by Sources:

Comments - Policy


Articles of potential interest

Remarks on the Monge–Kantorovich problem in the discrete setting

Haïm Brezis

C. R. Math (2018)


Multi-marginal Monge–Kantorovich transport problems: A characterization of solutions

Abbas Moameni

C. R. Math (2014)


The Plateau problem from the perspective of optimal transport

Haim Brezis; Petru Mironescu

C. R. Math (2019)