mlsanityData to 7 Oct 2026

Wasserstein barycenters can be computed in polynomial time in fixed dimension

arXiv 2006.08012 ↗First posted 14 Jun 2020math.OC cs.CG cs.DScited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

23 papers.

Sort:

  1. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  2. 2021Wasserstein barycenters are NP-hard to computecited by 28
  3. 2022Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfecited by 22
  4. 2022The Multimarginal Optimal Transport Formulation of Adversarial Multiclass Classificationcited by 21
  5. 2021Learning Prototype-oriented Set Representations for Meta-Learningcited by 19
  6. 2023Multimarginal generative modeling with stochastic interpolantscited by 17
  7. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  8. 2025RegGS: Unposed Sparse Views Gaussian Splatting with 3DGS Registrationcited by 12
  9. 2021Hierarchical Optimal Transport for Unsupervised Domain Adaptationcited by 10
  10. 2023Doubly Regularized Entropic Wasserstein Barycenterscited by 10
  11. 2021A novel notion of barycenter for probability distributions based on optimal weak mass transportcited by 5
  12. 2024Differentially Private Post-Processing for Fair Regressioncited by 5
11 more
  1. 2021Landmarks Augmentation with Manifold-Barycentric Oversamplingcited by 4
  2. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  3. 2024Low-dimensional approximations of the conditional law of Volterra processes: a non-positive curvature approachcited by 3
  4. 2025Differentially Private Wasserstein Barycenterscited by 2
  5. 2022Stability of Entropic Wasserstein Barycenters and application to random geometric graphscited by 1
  6. 2024Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problemscited by 1
  7. 2025Finite sample bounds for barycenter estimation in geodesic spacescited by 1
  8. 2022Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenterscited by 0
  9. 2023Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterationscited by 0
  10. 2026Hierarchical Wasserstein Merging for Multi-Domain Multi-Task Learning: From Specialists to a Generalistcited by 0
  11. 2026A Sub-4 Approximation for Fair k-Meanscited by 0