Time: 4:00 - 5:00pm Venue: BR 3.01, Bancroft Road Teaching Room, QMUL
Title: Submodular Optimisation: Algorithms and Applications
Speaker: Dr Justin Ward, School of Mathematical Sciences
Abstract: In this talk, I will discuss some general algorithmic techniques that can be applied to a wide variety of discrete optimisation problems whose objectives satisfy a natural "diminishing returns" property. This property, called "submodularity," can be viewed as a discrete analogue of convexity, and arises in several settings, including: network analysis, machine learning, economics, and constraint satisfaction problems. This property allows us to derive strong, worst-case performance guarantees for several natural heuristics such as greedy and local search algorithms. In this talk I will review the basic definitions, give some sample applications from various settings, and discuss popular algorithms for submodular optimisation. I will also discuss some recent joint work with Alina Ene, Huy Nguyen, and Raphael Barbosa that gives distributed algorithms for large scale problems with guarantees nearly matching those attainable in the standard, centralised setting.
Bio: Justin Ward is a Lecturer in Optimisation and Operational Research in the School of Mathematical Sciences at Queen Mary University of London, which he joined in 2017. He received his PhD in Computer Science in 2012 from the University of Toronto, and previously worked as a postdoc at the University of Warwick and EPFL. His research interests include the development and analysis of algorithms for hard combinatorial optimisation problems in theoretical computer science and operational research. His current research concerns approximation algorithms, combinatorial optimisation, and optimisation of submodular functions, with a particular focus on simple, combinatorial algorithms, such as local search and greedy algorithms.