Wasserstein Barycenters Are NP-Hard to Compute

DOI10.1137/21M1390062MaRDI QIDQ5065469

Enric Boix-Adserà, Jason M. Altschuler

Publication date: 21 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.01100

zbMATH Keywords

computational complexitycurse of dimensionalityNP-hardnessinapproximabilityWasserstein barycentersoptimal transport barycenters

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Polynomial-time algorithms for multimarginal optimal transport problems with structure ⋮ Discrete Optimal Transport with Independent Marginals is #P-Hard ⋮ Bayesian learning with Wasserstein barycenters ⋮ A column generation approach to the discrete barycenter problem ⋮ Simple approximative algorithms for free-support Wasserstein barycenters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational Optimal Transport: With Applications to Data Science
• A fixed-point approach to barycenters in Wasserstein space
• Discrete Wasserstein barycenters: optimal transport for discrete data
• Matching for teams
• Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the computational complexity of finding a sparse Wasserstein barycenter
• Hardness results for multimarginal optimal transport problems
• Convolutional wasserstein distances
• Barycenters in the Wasserstein Space
• Numerical methods for matching for teams and Wasserstein barycenters
• Combinatorics and Geometry of Transportation Polytopes: An Update
• Fast Discrete Distribution Clustering Using Wasserstein Barycenter With Sparse Support
• An entropy minimization approach to second-order variational mean-field games
• Reducibility among Combinatorial Problems
• Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
• Multi-Marginal Optimal Transport and Probabilistic Graphical Models
• Iterative Bregman Projections for Regularized Transportation Problems
• Computational Complexity
• A Numerical Method to Solve Multi-Marginal Optimal Transport Problems with Coulomb Cost

This page was built for publication: Wasserstein Barycenters Are NP-Hard to Compute