The simplified Wasserstein barycenter problem consists in selecting one point from $k$ given sets, each set consisting of $n$ points, with the aim of minimizing the sum of distances to the barycenter of the $k$ points chosen. This problem is known to be NP-hard. We compute the Wasserstein barycenter by exploiting the Euclidean distance matrix structure to obtain a facially reduced doubly nonnegative, \DNNp, relaxation. The facial reduction provides provides a natural splitting for applying the Peaceman-Rachford method to the \DNN relaxation. Our numerical tests are surprisingly successful on random problems, as they generally find the provable exact solution from the \DNN relaxation. However, we see that there is a duality gap for problems with highly symmetrized structure. We then propose a method to address this issue.

(This is joint work with Abdo Alfaki, Leo Woosuk Jung, Walaa M. Mourse)