Back to Search
Start Over
Rigidity of Kantorovich solutions in discrete Optimal Transport
- 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
- Subjects :
- Mathematics - Optimization and Control
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2311.18764
- Document Type :
- Working Paper