We present a new ansatz space for the general symmetric multi-marginal Kantorovich optimal transport problem on finite state spaces which reduces the number of unknowns from $tbinom{N+ell-1}{ell-1}$ to $ellcdot(N+1)$, where $ell$ is the number of marginal states and $N$ the number of marginals. The new ansatz space is a careful low-dimensional enlargement of the Monge class, which corresponds to $ellcdot(N-1)$ unknowns, and cures the insufficiency of the Monge ansatz, i.e. we show that the Kantorovich problem always admits a minimizer in the enlarged class, for arbitrary cost functions. Our results apply, in particular, to the discretization of multi-marginal optimal transport with Coulomb cost in three dimensions, which has received much recent interest due to its emergence as the strongly correlated limit of Hohenberg-Kohn density functional theory. In this context $N$ corresponds to the number of particles, motivating the interest in large $N$.
Download