Pure Maths Colloquium: Justin Ward

A wide variety of optimization problems at the heart of machine learning, economics, and operations research can be cast as constrained submodular maximization problems. Unfortunately, in many emerging applications, the resulting submodular optimization problems are too large to be solved (or even stored) on a single machine. In this talk, I will describe a new framework for distributed submodular maximization. The framework is easily stated in the popular MapReduce model of computation, and provides a general condition under which centralised algorithms can be transformed into distributed algorithms with almost no loss in the approximation guarantee. This talk is based on joint work with Rafael da Pont Barbosa, Alina Ene, and Huy Nguyen.