Wednesday, March 11 2020
9:00am - 11:00am
PhD Thesis Presentation
Algorithms for Discrete Barycenters

Abstract: Discrete barycenters are solutions to a class of optimal transport problems in which the input are probability measures with finite support sets. Exact solutions can be computed through exponential-sized linear programs, a prohibitively expensive approach. Efficient computations are highly desirable, as applications arise in a variety of fields including economics, physics, statistics, manufacturing, facility locations, and more. To illustrate the extremes of problem difficulty, we focus on two examples: a best-case setting based on the MNIST Digits Data set and a worst-case setting based on Denver crime locations. We describe improved linear programming models and solving strategies for each setting, supported with implementations that demonstrate significant improvements in total running time and memory requirements. We conclude with a brief examination of our proof that a decision variant of the problem is computationally hard; that is, through a reduction from planar three-dimensional matching, we show it is NP-hard to decide if there exists a solution with non-mass-splitting transport cost and support set size below prescribed bounds.
Speaker:Stephen Patterson

Download as iCalendar