Published Paper
Inserted: 23 dec 2022
Last Updated: 20 nov 2026
Journal: IMA Journal of Numerical Analysis
Volume: 46
Number: 5
Pages: 2231-2256
Year: 2026
Doi: 10.1093/imanum/draf067
Abstract:
The purpose of this paper is to introduce a new numerical method to solve multi-marginal optimal transport problems with pairwise interaction costs. The complexity of multi-marginal optimal transport generally scales exponentially in the number of marginals $m$. We introduce a one parameter family of cost functions that interpolates between the original and a special cost function for which the problem's complexity scales linearly in $m$. We then show that the solution to the original problem can be recovered by solving an ordinary differential equation in the parameter $\epsilon$, whose initial condition corresponds to the solution for the special cost function mentioned above; we then present some simulations, using both explicit Euler and explicit higher order Runge-Kutta schemes to compute solutions to the ODE, and, as a result, the multi-marginal optimal transport problem.
Download: