Intrinsic Sparsity of Kantorovich Solutions

Abstract

Let $X,Y$ be two finite sets of points having $\#X=m$ and $\#Y=n$ points with $\mu =(1/m){\sum }_{i=1}^m{\delta }_{x_i}$ and $\nu =(1/n){\sum }_{j=1}^n{\delta }_{y_j}$ 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 (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$.