  Discrete barycenters are the optimal solutions to mass transport problems for
a set of discrete measures. Such transport problems arise in many applications
of operations research and statistics. The best known algorithms for exact
barycenters are based on linear programming, but these programs scale
exponentially in the number of measures, making them prohibitive for practical
purposes.
  In this paper, we improve on these algorithms. First, by using the optimality
conditions to restrict the search space, we provide a reduced linear program
that contains dramatically fewer variables compared to previous formulations.
Second, we recall a proof from the literature, which lends itself to a linear
program that has not been considered for computations. We show that this second
formulation is the best model for data in general position. Third, we combine
the two programs into a single hybrid model that retains the best properties of
both formulations for partially structured data.
  We study these models through an analysis of their scaling in size, the
hardness of the required preprocessing, and computational experiments. In doing
so, we show that each of the improved linear programs becomes the best model
for different types of data.
