  The \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 consisting of $n$ points, with the aim of minimizing the sum of
distances to the barycenter of the $k$ chosen points. This problem is also
known as the cheapest hub problem. 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 a natural splitting for applying the symmetric
alternating directions method of multipliers (\sADMM) to the \DNN relaxation.
The \sADMM method exploits structure in the subproblems to find strong upper
and lower bounds. In addition, we extend the problem to allow varying $n_j$
points for the $j$-th set.
  The purpose of this paper is twofold. First we want to illustrate the
strength of this \DNN relaxation with a splitting approach. Our numerical tests
then illustrate the surprising success on random problems, as we generally,
efficiently, find the provable exact solution of this NP-hard problem.
Comparisons with current commercial software illustrate this surprising
efficiency. However, we demonstrate and prove that there is a duality gap for
problems with \emph{enough} multiple optimal solutions, and that this arises
from problems with highly symmetrized structure.
