On the computational complexity of finding a sparse Wasserstein barycenter

DOI10.1007/s10878-021-00713-5MaRDI 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 theory; sparsity; optimal transport; Wasserstein barycenter; 3-dimensional matching

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B06: Transportation, logistics and supply chain management

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

90B80: Discrete location and assignment

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)