# A Column Generation Approach to the Discrete Barycenter Problem

arXiv: https://arxiv.org/abs/1907.01541 · HTML: https://mlsanity.com/paper/1907.01541/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2019.

## Built on by (most cited first, 1 of 1)

- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)

## Abstract (arXiv)

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.