Back to Search Start Over

Rigidity of Kantorovich solutions in discrete Optimal Transport

Authors :
Johnson, Alexander Bruce
Steinerberger, Stefan
Publication Year :
2023

Abstract

We study optimal transport plans from $m$ equally weighted points (with weights $1/m$) to $n$ equally weighted points (with weights $1/n$). The Birkhoff-von Neumann Theorem implies that if $m=n$, then the optimal transport plan can be realized by a bijective map: the mass from each $x_i$ is sent to a unique $y_j$. This is impossible when $m \neq n$, however, a certain degree of rigidity prevails. We prove, assuming w.l.o.g. $m < n$, that for generic transport costs the optimal transport plan sends mass from each source $x_i$ to $n/m \leq \mbox{different targets} \leq n/m + m-1$. Moreover, the average target receives mass from $\leq 1 + m/\sqrt{n}$ sources. Stronger results might be true: in experiments, one observes that each source tends to distribute its mass over roughly $n/m +c$ different targets where $c$ appears to be rather small.<br />Comment: We discovered that the result is implied by a known fact (details on page 1). This manuscript is not submitted anywhere

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2311.18764
Document Type :
Working Paper