

2013/03/28, FDA 232, 10:00  11:00
The Unexpected Power of Local Search
Yuval
Filmus
, PhD Candidate, University of Toronto, Computer Science
Abstract:
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
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 nonoblivious 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.


