# Monotone submodular maximization over a matroid

 Computer Science/Discrete Mathematics Seminar II Topic: Monotone submodular maximization over a matroid Speaker: Yuval Filmus Affiliation: Member, School of Mathematics Date: Tuesday, October 7 Time/Room: 10:30am - 12:30pm/S-101 Video Link: http://video.ias.edu/csdm/2014/1007-YuvalFilmus

Monotone submodular maximization over a matroid (MSMM) is a fundamental optimization problem generalizing Maximum Coverage and MAX-SAT. Maximum Coverage is NP-hard to approximate better than $1-1/e$, an approximation ratio obtained by the greedy algorithm. The performance of the greedy algorithm deteriorates to $1/2$ on the more general problem of MAX-SAT. Recently, Vondrak et al. designed a sophisticated algorithm attaining the optimal approximation ratio $1-1/e$ for MSMM. Their algorithm finds a fractional solution for a continuous relaxation of MSMM, and then rounds it to a solution of the original problem. We present a completely different algorithm which employs the paradigm of non-oblivious local search and is completely combinatorial.