Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method

Woosuk L. Jung, Henry Wolkowicz

The so-called \emph{simplified} Wasserstein barycenter problem, also known as the cheapest hub problem, consists in selecting one point from each of $k$ given sets, each set consis…