# Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure

arXiv: https://arxiv.org/abs/2008.03006 · HTML: https://mlsanity.com/paper/2008.03006/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2020.

## Built on by (most cited first, 15 of 15)

- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Convergence Rates for Regularized Optimal Transport via Quantization](https://mlsanity.com/paper/2208.14391/) (2022)
- [Trajectory Inference with Smooth Schr"odinger Bridges](https://mlsanity.com/paper/2503.00530/) (2025)
- [Sliced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2102.07115/) (2021)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Stochastic Learning of Computational Resource Usage as Graph Structured Multimarginal Schr"odinger Bridge](https://mlsanity.com/paper/2405.12463/) (2024)
- [Neural Estimation for Scaling Entropic Multimarginal Optimal Transport](https://mlsanity.com/paper/2506.00573/) (2025)
- [Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport](https://mlsanity.com/paper/2210.13630/) (2022)
- [Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport](https://mlsanity.com/paper/2503.09449/) (2025)
- [Optimal Multimarginal Schr"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices](https://mlsanity.com/paper/2509.10626/) (2025)
- [An algorithmic solution to the Blotto game using multi-marginal couplings](https://mlsanity.com/paper/2202.07318/) (2022)
- [Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS](https://mlsanity.com/paper/2605.05330/) (2026)

## Abstract (arXiv)

Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n,k) time. We develop a unified algorithmic framework for solving MOT in poly(n,k) time by characterizing the "structure" that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes it much simpler to develop poly(n,k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle -- which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing poly(n,k) time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime; moreover, we provide the first poly(n,k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n,k) time algorithms, even for approximate computation. Together, these three structures encompass many -- if not most -- current applications of MOT.