On the computational complexity of finding a sparse Wasserstein barycenter

DOI10.1007/s10878-021-00713-5OpenAlexW3133997403MaRDI QIDQ2025065

Steffen Borgwardt, Stephan Patterson

Publication date: 11 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

complexity theorysparsityoptimal transportWasserstein barycenter3-dimensional matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Transportation, logistics and supply chain management (90B06) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Wasserstein Barycenters Are NP-Hard to Compute ⋮ Randomized Wasserstein Barycenter Computation: Resampling with Statistical Guarantees ⋮ Location Problems with Cutoff ⋮ Unnamed Item ⋮ A column generation approach to the discrete barycenter problem ⋮ Hardness results for multimarginal optimal transport problems

Cites Work

• Discrete Wasserstein barycenters: optimal transport for discrete data
• Geometric three-dimensional assignment problems
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Planar 3DM is NP-complete
• Fast Entropic Regularized Optimal Transport Using Semidiscrete Cost Approximation
• Iterative Bregman Projections for Regularized Transportation Problems
• Convergence of Entropic Schemes for Optimal Transport and Gradient Flows
• Optimal Transport

This page was built for publication: On the computational complexity of finding a sparse Wasserstein barycenter