On the computational complexity of finding a sparse Wasserstein barycenter

Steffen Borgwardt () and Stephan Patterson ()
Additional contact information
Steffen Borgwardt: University of Colorado Denver
Stephan Patterson: Louisiana State University Shreveport

Journal of Combinatorial Optimization, 2021, vol. 41, issue 3, No 8, 736-761

Abstract: Abstract The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of probability measures with finite support. In this paper, we show that finding a barycenter of sparse support is hard, even in dimension 2 and for only 3 measures. We prove this claim by showing that a special case of an intimately related decision problem SCMP—does there exist a measure with a non-mass-splitting transport cost and support size below prescribed bounds? Is NP-hard for all rational data. Our proof is based on a reduction from planar 3-dimensional matching and follows a strategy laid out by Spieksma and Woeginger (Eur J Oper Res 91:611–618, 1996) for a reduction to planar, minimum circumference 3-dimensional matching. While we closely mirror the actual steps of their proof, the arguments themselves differ fundamentally due to the complex nature of the discrete barycenter problem. Containment of SCMP in NP will remain open. We prove that, for a given measure, sparsity and cost of an optimal transport to a set of measures can be verified in polynomial time in the size of a bit encoding of the measure. However, the encoding size of a barycenter may be exponential in the encoding size of the underlying measures.

Keywords: Wasserstein barycenter; Optimal transport; Sparsity; Complexity theory; 3-Dimensional matching; 68Q17; 68Q25; 90B06; 90B80; 05C70 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00713-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:3:d:10.1007_s10878-021-00713-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00713-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().