Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars profile

Fall 2015 Schedule
Winter 2016 Schedule

2013/03/28, FDA 232, 10:00 - 11:00

The Unexpected Power of Local Search
Yuval Filmus , PhD Candidate, University of Toronto, Computer Science


Yuval Filmus is a Ph.D. candidate in Computer Science in University of Toronto, advised by Prof. Toni Pitassi. His research interests include approximation algorithms, computational complexity, proof complexity, analysis of Boolean functions, and combinatorics. He received his masters degree in Computer Science from the Weizmann institute

Biography of Speaker:

The difficulty of solving combinatorial optimization problems efficiently has led to the design of approximation algorithms. Unfortunately, approximation algorithms are often quite complicated and specialized, which limits their applicability. In this talk, we discuss a fundamental combinatorial optimization problem, monotone submodular maximization over a matroid constraint (MSMM). This problem generalizes classical problems such as Maximum Coverage and Maximum Satisfiability. The simple greedy algorithm achieves the best possible approximation ratio for Maximum Coverage. However, for the more general MSMM problem, achieving the best approximation ratio required the sophisticated continuous greedy algorithm. We present an elementary non-oblivious local search algorithm, which is also theoretically optimal. Our algorithm is much simpler than the existing continuous greedy algorithm, and moreover it may generalize to new situations in which the continuous greedy approach fails.