  The discrete Wasserstein barycenter problem is a minimum-cost mass transport
problem for a set of discrete probability measures. Although an exact
barycenter is computable through linear programming, the underlying linear
program can be extremely large. For worst-case input, a best known linear
programming formulation is exponential in the number of variables, but has a
low number of constraints, making it an interesting candidate for column
generation.
  In this paper, we devise and study two column generation strategies: a
natural one based on a simplified computation of reduced costs, and one through
a Dantzig-Wolfe decomposition. For the latter, we produce efficiently solvable
subproblems, namely, a pricing problem in the form of a classical
transportation problem. The two strategies begin with an efficient computation
of an initial feasible solution. While the structure of the constraints leads
to the computation of the reduced costs of all remaining variables for setup,
both approaches may outperform a computation using the full program in speed,
and dramatically so in memory requirement. In our computational experiments, we
exhibit that, depending on the input, either strategy can become a best choice.
