# Wasserstein barycenters can be computed in polynomial time in fixed dimension

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

## Key facts

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

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

- [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classification](https://mlsanity.com/paper/2204.12676/) (2022)
- [Learning Prototype-oriented Set Representations for Meta-Learning](https://mlsanity.com/paper/2110.09140/) (2021)
- [Multimarginal generative modeling with stochastic interpolants](https://mlsanity.com/paper/2310.03695/) (2023)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [RegGS: Unposed Sparse Views Gaussian Splatting with 3DGS Registration](https://mlsanity.com/paper/2507.08136/) (2025)
- [Hierarchical Optimal Transport for Unsupervised Domain Adaptation](https://mlsanity.com/paper/2112.02073/) (2021)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [A novel notion of barycenter for probability distributions based on optimal weak mass transport](https://mlsanity.com/paper/2102.13380/) (2021)
- [Differentially Private Post-Processing for Fair Regression](https://mlsanity.com/paper/2405.04034/) (2024)
- [Landmarks Augmentation with Manifold-Barycentric Oversampling](https://mlsanity.com/paper/2104.00925/) (2021)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [Low-dimensional approximations of the conditional law of Volterra processes: a non-positive curvature approach](https://mlsanity.com/paper/2405.20094/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Stability of Entropic Wasserstein Barycenters and application to random geometric graphs](https://mlsanity.com/paper/2210.10535/) (2022)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [Finite sample bounds for barycenter estimation in geodesic spaces](https://mlsanity.com/paper/2502.14069/) (2025)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations](https://mlsanity.com/paper/2307.13370/) (2023)
- [Hierarchical Wasserstein Merging for Multi-Domain Multi-Task Learning: From Specialists to a Generalist](https://mlsanity.com/paper/2609.06406/) (2026)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with textrmpolylog(1/varepsilon) runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.