mlsanityData to 14 Oct 2026

Wasserstein barycenters are NP-hard to compute

arXiv 2101.01100 ↗First posted 4 Jan 2021math.OC cs.CC cs.DScited by 28

Not on the map. Why?

Abstract (arXiv)

Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a fundamental problem in geometry which has recently attracted considerable attention due to many applications in data science. While there exist polynomial-time algorithms in any fixed dimension, all known running times suffer exponentially in the dimension. It is an open question whether this exponential dependence is improvable to a polynomial dependence. This paper proves that unless P=NP, the answer is no. This uncovers a "curse of dimensionality" for Wasserstein barycenter computation which does not occur for Optimal Transport computation. Moreover, our hardness results for computing Wasserstein barycenters extend to approximate computation, to seemingly simple cases of the problem, and to averaging probability distributions in other Optimal Transport metrics.

Key facts. Cited by 28 papers in the map (data through 14 Oct 2026). Builds on 27 of its 55 references that are in the map. First posted on arXiv 4 Jan 2021.

Builds on

27 of 55 references.

References · 27

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  2. 2018Computational Optimal Transportcited by 780
  3. 2013Fast Computation of Wasserstein Barycenterscited by 216
  4. 2018Statistical Aspects of Wasserstein Distancescited by 203
  5. 2017Multilevel Clustering via Wasserstein Meanscited by 49
  6. 2015Scalable Bayes via Barycenter in Wasserstein Spacecited by 44
  7. 2020Debiased Sinkhorn barycenterscited by 34
  8. 2015Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Supportcited by 30
  9. 2020Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithmcited by 29
  10. 2019Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithmcited by 27
  11. 2015Fast Optimal Transport Averaging of Neuroimaging Datacited by 26
  12. 2020Wasserstein barycenters can be computed in polynomial time in fixed dimensioncited by 23
15 more
  1. 2015Discrete Wasserstein Barycenters: Optimal Transport for Discrete Datacited by 20
  2. 2018Distilled Wasserstein Learning for Word Embedding and Topic Modelingcited by 18
  3. 2020Estimating Barycenters of Measures in High Dimensionscited by 18
  4. 2020Polynomial-time algorithms for Multimarginal Optimal Transport problems with structurecited by 15
  5. 2017Parallel Streaming Wasserstein Barycenterscited by 14
  6. 2020Multi-marginal optimal transport and probabilistic graphical modelscited by 13
  7. 2020Hardness results for Multimarginal Optimal Transport problemscited by 13
  8. 2018Context Mover's Distance & Barycenters: Optimal Transport of Contexts for Building Representationscited by 11
  9. 2017Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithmcited by 9
  10. 2018An entropy minimization approach to second-order variational mean-field gamescited by 9
  11. 2020Sinkhorn Barycenter via Functional Gradient Descentcited by 9
  12. 2019On the Computational Complexity of Finding a Sparse Wasserstein Barycentercited by 8
  13. 2018Probabilistic Multilevel Clustering via Composite Transportation Distancecited by 6
  14. 2017An LP-based, Strongly-Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenterscited by 4
  15. 2019On the Complexity of Approximating Wasserstein Barycentercited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 3; 2024: 7; 2025: 7; 2026: 2.

28 papers.

Sort:

By area:

  1. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  2. 2022The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classificationcited by 21
  3. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  4. 2025RegGS: Unposed Sparse Views Gaussian Splatting with 3DGS Registrationcited by 13
  5. 2023Energy-Guided Continuous Entropic Barycenter Estimation for General Costscited by 12
  6. 2025Trajectory Inference with Smooth Schr"odinger Bridgescited by 11
  7. 2023Doubly Regularized Entropic Wasserstein Barycenterscited by 10
  8. 2024Simultaneous linear connectivity of neural networks modulo permutationcited by 10
  9. 2021Projection Robust Wasserstein Barycenterscited by 8
  10. 2024ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Modelscited by 6
  11. 2021Sliced Multi-Marginal Optimal Transportcited by 5
  12. 2021Sampling From the Wasserstein Barycentercited by 5
16 more
  1. 2024An Optimal Transport Approach for Computing Adversarial Training Lower Bounds in Multiclass Classificationcited by 5
  2. 2022Discrete Optimal Transport with Independent Marginals is #P-Hardcited by 3
  3. 2022Wasserstein Distributionally Robust Optimization with Wasserstein Barycenterscited by 3
  4. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  5. 2024Distributional Matrix Completion via Nearest Neighbors in the Wasserstein Spacecited by 3
  6. 2024Multi-Output Distributional Fairness via Post-Processingcited by 2
  7. 2025Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysiscited by 2
  8. 2025Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentrescited by 2
  9. 2025Finite sample bounds for barycenter estimation in geodesic spacescited by 1
  10. 2025Wasserstein Gradient Flows for Scalable and Regularized Barycenter Computationcited by 1
  11. 2026Static and Dynamic Approaches to Computing Barycenters of Probability Measures on Graphscited by 1
  12. 2022Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenterscited by 0
  13. 2023Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterationscited by 0
  14. 2024Kullback-Leibler Barycentre of Stochastic Processescited by 0
  15. 2025Differentiable Expectation-Maximisation and Applications to Gaussian Mixture Model Optimal Transportcited by 0
  16. 2026Optimal Transport for Efficient, Unsupervised Anomaly Detection on Industrial Datacited by 0