# Hardness results for Multimarginal Optimal Transport problems

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2020.

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

- [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)
- [Contrasting Multiple Representations with the Multi-Marginal Matching Gap](https://mlsanity.com/paper/2405.19532/) (2024)
- [Sliced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2102.07115/) (2021)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Matching for causal effects via multimarginal unbalanced optimal transport](https://mlsanity.com/paper/2112.04398/) (2021)
- [Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems](https://mlsanity.com/paper/2103.12624/) (2021)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Neural Estimation for Scaling Entropic Multimarginal Optimal Transport](https://mlsanity.com/paper/2506.00573/) (2025)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport](https://mlsanity.com/paper/2112.00838/) (2021)
- [An algorithmic solution to the Blotto game using multi-marginal couplings](https://mlsanity.com/paper/2202.07318/) (2022)
- [Same Predictions, Different Harms: Causal Auditing of Patient World Models](https://mlsanity.com/paper/2610.05198/) (2026)

## Abstract (arXiv)

Multimarginal Optimal Transport (MOT) is the problem of linear programming over joint probability distributions with fixed marginals. A key issue in many applications is the complexity of solving MOT: the linear program has exponential size in the number of marginals k and their support sizes n. A recent line of work has shown that MOT is poly(n,k)-time solvable for certain families of costs that have poly(n,k)-size implicit representations. However, it is unclear what further families of costs this line of algorithmic research can encompass. In order to understand these fundamental limitations, this paper initiates the study of intractability results for MOT. Our main technical contribution is developing a toolkit for proving NP-hardness and inapproximability results for MOT problems. We demonstrate this toolkit by using it to establish the intractability of a number of MOT problems studied in the literature that have resisted previous algorithmic efforts. For instance, we provide evidence that repulsive costs make MOT intractable by showing that several such problems of interest are NP-hard to solve--even approximately.