Wasserstein Barycenters Are NP-Hard to Compute
From MaRDI portal
(Redirected from Wasserstein Barycenters Are NP-Hard to Compute)
Recommendations
- scientific article; zbMATH DE number 7370561
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- On the computational complexity of finding a sparse Wasserstein barycenter
- Simple approximative algorithms for free-support Wasserstein barycenters
- On the computation of Wasserstein barycenters
Cites work
- A fixed-point approach to barycenters in Wasserstein space
- A numerical method to solve multi-marginal optimal transport problems with Coulomb cost
- An entropy minimization approach to second-order variational mean-field games
- Barycenters in the Wasserstein space
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorics and geometry of transportation polytopes: an update
- Computational Complexity
- Computational optimal transport. With applications to data sciences
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Discrete Wasserstein barycenters: optimal transport for discrete data
- Fast Discrete Distribution Clustering Using Wasserstein Barycenter With Sparse Support
- Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
- Hardness results for multimarginal optimal transport problems
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 7370561 (Why is no real title available?)
- scientific article; zbMATH DE number 7415088 (Why is no real title available?)
- scientific article; zbMATH DE number 3053873 (Why is no real title available?)
- Iterative Bregman projections for regularized transportation problems
- Matching for teams
- Multi-Marginal Optimal Transport and Probabilistic Graphical Models
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
- Numerical methods for matching for teams and Wasserstein barycenters
- On the computational complexity of finding a sparse Wasserstein barycenter
- Reducibility among combinatorial problems
- Scalable Bayes via barycenter in Wasserstein space
Cited in
(19)- A column generation approach to the discrete barycenter problem
- Simple approximative algorithms for free-support Wasserstein barycenters
- scientific article; zbMATH DE number 7370561 (Why is no real title available?)
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- Bayesian learning with Wasserstein barycenters
- Wasserstein barycenters are NP-hard to compute
- Proxying credit curves via Wasserstein distances
- Wasserstein medians: robustness, PDE characterization, and numerics
- Computing Wasserstein barycenters via operator splitting: the method of averaged marginals
- Sparse Wasserstein barycenters and application to reduced order modeling
- Mathematical imaging and surface processing. Abstracts from the workshop held February 2--7, 2025
- Concentration of empirical barycenters in metric spaces
- An optimal transport approach for computing adversarial training lower bounds in multiclass classification
- Expected value and a Cayley-Menger-type formula for the generalized earth mover's distance
- Kullback-Leibler barycenter of stochastic processes
- Geometry of the space of partitioned networks: a unified theoretical and computational framework
- Doubly regularized entropic Wasserstein barycenter
- Closing the gap: efficient algorithms for discrete Wasserstein barycenters
This page was built for publication: Wasserstein Barycenters Are NP-Hard to Compute
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065469)
