  Discrete Wasserstein barycenters correspond to optimal solutions of
transportation problems for a set of probability measures with finite support.
Discrete barycenters are measures with finite support themselves and exhibit
two favorable properties: there always exists one with a provably sparse
support, and any optimal transport to the input measures is non-mass splitting.
  It is open whether a discrete barycenter can be computed in polynomial time.
It is possible to find an exact barycenter through linear programming, but
these programs may scale exponentially. In this paper, we prove that there is a
strongly-polynomial 2-approximation algorithm based on linear programming.
First, we show that an exact computation over the union of supports of the
input measures gives a tight 2-approximation. This computation can be done
through a linear program with setup and solution in strongly-polynomial time.
The resulting measure is sparse, but an optimal transport may split mass. We
then devise a second, strongly-polynomial algorithm to improve this measure to
one with a non-mass splitting transport of lower cost. The key step is an
update of the possible support set to resolve mass split.
  Finally, we devise an iterative scheme that alternates between these two
algorithms. The algorithm terminates with a 2-approximation that has both a
sparse support and an associated non-mass splitting optimal transport. We
conclude with some sample computations and an analysis of the scaling of our
algorithms, exhibiting vast improvements in running time over exact LP-based
computations and low practical errors.
