# On the Complexity of Approximating Multimarginal Optimal Transport

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

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

- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Extended Flow Matching: a Method of Conditional Generation with Generalized Continuity Equation](https://mlsanity.com/paper/2402.18839/) (2024)
- [Trajectory Inference with Smooth Schr"odinger Bridges](https://mlsanity.com/paper/2503.00530/) (2025)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Contrasting Multiple Representations with the Multi-Marginal Matching Gap](https://mlsanity.com/paper/2405.19532/) (2024)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Sliced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2102.07115/) (2021)
- [An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classification](https://mlsanity.com/paper/2401.09191/) (2024)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Interpolation for Robust Learning: Data Augmentation on Wasserstein Geodesics](https://mlsanity.com/paper/2302.02092/) (2023)
- [Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies](https://mlsanity.com/paper/2407.10000/) (2024)
- [Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2501.14635/) (2025)
- [Neural Estimation for Scaling Entropic Multimarginal Optimal Transport](https://mlsanity.com/paper/2506.00573/) (2025)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [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)
- [Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport](https://mlsanity.com/paper/2112.00838/) (2021)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [An algorithmic solution to the Blotto game using multi-marginal couplings](https://mlsanity.com/paper/2202.07318/) (2022)
- [Efficient Forecasting of Large Scale Hierarchical Time Series via Multilevel Clustering](https://mlsanity.com/paper/2205.14104/) (2022)
- [HOT-POT: Optimal Transport for Sparse Stereo Matching](https://mlsanity.com/paper/2601.12423/) (2026)
- [Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schr"odinger Bridges](https://mlsanity.com/paper/2605.10917/) (2026)
- [DisPOSE: Projected Polystochastic Diffusion for Self-Supervised Multi-View 3D Human Pose Estimation](https://mlsanity.com/paper/2606.07419/) (2026)
- [Scaling Online Optimal Transport Minibatches for Flow Matching](https://mlsanity.com/paper/2610.18838/) (2026)

## Abstract (arXiv)

We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between m discrete probability distributions supported each on n support points. First, we show that the standard linear programming (LP) representation of the MOT problem is not a minimum-cost flow problem when m ≥ 3. This negative result implies that some combinatorial algorithms, e.g., network simplex method, are not suitable for approximating the MOT problem, while the worst-case complexity bound for the deterministic interior-point algorithm remains a quantity of tildeO(n3m). We then propose two simple and textitdeterministic algorithms for approximating the MOT problem. The first algorithm, which we refer to as textitmultimarginal Sinkhorn algorithm, is a provably efficient multimarginal generalization of the Sinkhorn algorithm. We show that it achieves a complexity bound of tildeO(m3nmvarepsilon-2) for a tolerance varepsilon ∈ (0, 1). This provides a first textitnear-linear time complexity bound guarantee for approximating the MOT problem and matches the best known complexity bound for the Sinkhorn algorithm in the classical OT setting when m = 2. The second algorithm, which we refer to as textitaccelerated multimarginal Sinkhorn algorithm, achieves the acceleration by incorporating an estimate sequence and the complexity bound is tildeO(m3nm+1/3varepsilon-4/3). This bound is better than that of the first algorithm in terms of 1/varepsilon, and accelerated alternating minimization algorithm~citepTupitsa-2020-Multimarginal in terms of n. Finally, we compare our new algorithms with the commercial LP solver textscGurobi. Preliminary results on synthetic data and real images demonstrate the effectiveness and efficiency of our algorithms.