Optimal Transport (OT) is the mathematical "gold standard" for moving mass from one distribution to another with minimum effort. In its classic form, it solves a bipartite matching problem: how do we pair points in distribution $A$ with points in distribution $B$? However, many modern problems—from aligning multiple biological datasets to averaging complex shapes—require matching $k$ distributions simultaneously. This is the domain of Multi-marginal Optimal Transport (MOT).
While standard OT is computationally manageable, MOT is notoriously difficult. As Jason Altschuler and Enric Boix-Adserà describe in Hardness results for Multimarginal Optimal Transport problems, MOT is a "computational boogeyman." If each of the $k$ distributions has $n$ points, the potential transport plan is not a matrix, but a $k$-dimensional tensor with $n^k$ entries. This exponential explosion makes direct optimization impossible for even modest values of $k$.
The Geometry of Consensus: Wasserstein Barycenters
The most intuitive application of MOT is the Wasserstein Barycenter—finding the "average" of several probability distributions. Unlike a pixel-wise average, which produces a blurry overlap of shapes, a Wasserstein barycenter respects the underlying geometry. For example, the barycenter of two shifted circles is a single circle located halfway between them.
Enric Boix-Adserà shows in High-precision Wasserstein barycenters in polynomial time that these barycenters provide a way to average data while preserving structural features. However, computing them is fundamentally harder than standard OT. Tianyi Lin, Nhat Ho, and Michael I. Jordan addressed this in Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm by developing FASTIBP, a deterministic algorithm that improves the complexity bounds for finding these geometric averages.
Breaking the Curse of Dimensionality
To make MOT practical, researchers look for "structure" that allows them to avoid the $n^k$ tensor.
- Graphical Structure: If the cost function decomposes according to a graph (like a tree or a chain), the problem becomes much easier. Jiaojiao Fan and Yongxin Chen 0002 propose A parallel framework for graphical optimal transport, which breaks the problem into smaller, parallelizable pieces.
- Polynomial-Time Solvability: Jason Altschuler and Enric Boix-Adserà proved in Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure that for certain costs (like low-rank or tree-structured costs), MOT can be solved in polynomial time, bypassing the exponential bottleneck.
- Hierarchical Decomposition: For tasks like network alignment, Zhichen Zeng introduced HOT in Hierarchical Multi-Marginal Optimal Transport for Network Alignment. By aligning clusters first and then nodes, they reduced memory costs by 1000x, making joint alignment of multiple networks feasible.
Dynamic Transport and Schrödinger Bridges
A major frontier for MOT is modeling processes that evolve over time, such as cell populations. In single-cell genomics, measuring a cell destroys it, so we only see "snapshots" of different populations at different times.
George Rapakoulias and Panagiotis Tsiotras developed GMMflow in Go With the Flow: Fast Diffusion for Gaussian Mixture Models to solve the Schrödinger Bridge (SB) problem—finding the most efficient path between distributions over time. By modeling distributions as Gaussian mixtures, they achieved massive speedups over neural solvers. Similarly, Panagiotis Theodoropoulos and Guan-Horng Liu introduced 3MSBM in Momentum Multi-Marginal Schrödinger Bridge Matching, which lifts dynamics into phase space to capture long-range temporal dependencies without expensive simulations.
Generative Modeling Across Multiple Domains
MOT also enables "all-to-all" translation in generative AI. Instead of training separate models to turn cats into dogs and dogs into celebrities, MOT allows for a single joint framework.
Michael S. Albergo and Eric Vanden‐Eijnden explored this in Multimarginal generative modeling with stochastic interpolants. By defining flows on a high-dimensional simplex, they enable simultaneous navigation between multiple data distributions. To handle the quadratic scaling of these transfers, Kotaro Ikeda and Kohei Hayashi proposed A2A-FM in Simultaneous Learning of Optimal Transports for Training All-to-All Flow-Based Condition Transfer Model, which learns transfers even when conditions are continuous or data is sparse.
Summary of the Shift
The research direction has moved from proving the theoretical existence of MOT solutions on manifolds—as seen in Young-Heon Kim and Brendan Pass's Multi-marginal optimal transport on Riemannian manifolds—to creating scalable, structured solvers. By exploiting graphical models, hierarchical decompositions, and generative flow matching, researchers are finally taming the "computational boogeyman" of multi-marginal transport.