An LP-based, Strongly Polynomial 2-Approximation Algorithm for Sparse Wasserstein Barycenters

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