Pankaj Agarwal, Duke University

Abstract

Given a d-dimensional continuous (resp. discrete) probability distribution A and a discrete distribution B, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from A to B; we assume $n$ to be the number of points in the support of the discrete distributions. This talk presents efficient approximation algorithms for both discrete and semi-discrete OT. It also presents an efficient algorithm for computing a Wasserstein barycenter of a family of discrete distributions.