Pure Maths Colloquium: Justin Ward

This talk is part of the Pure Maths Colloquium at the University of St Andrews. Check out our upcoming talks at https://theran.lt/pure-colloquium/.

Where: Lecture Theatre D
When: Nov 1 2018 @ 16.00
Video: Not recorded
Speaker: Justin Ward Queen Mary University of London
Title: Distributed submodular maximization on massive datasets

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.