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.