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 $\mu =\left(1/m\right)\left({\delta }_{{x}_{1}}+\cdots +{\delta }_{{x}_{m}}\right)$ and $\nu =\left(1/n\right)\left({\delta }_{{y}_{1}}+\cdots +{\delta }_{{y}_{n}}\right)$ 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 $\pi :X\to Y$. This is impossible when $m\ne n$. We observe that when $m\ne n$, there exists a solution of the Kantorovich problem such that the mass of each point in $X$ is moved to at most $n/gcd\left(m,n\right)$ different points in $Y$ and that, conversely, each point in $Y$ receives mass from at most $m/gcd\left(m,n\right)$ points in $X$.

Soient $X$ et $Y$ deux ensembles de points de cardinaux respectifs $m$ et $n$ ; et $\mu ,\nu$ 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 $m\ne n$, nous montrons que le problème de Kantorovitch admet une solution telle que chaque point de X se déplace vers au plus $n/\mathrm{pgcd}\left(m,n\right)$ points de Y, et réciproquement, chaque point de Y reçoit de la masse d’au plus $m/\mathrm{pgcd}\left(m,n\right)$ points de X.

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
@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  - 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 Stefan Steinerberger
%T Intrinsic Sparsity of Kantorovich solutions
%J Comptes Rendus. Mathématique
%D 2022
%P 1173-1175
%V 360
%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:

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)