|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Monotone submodular maximization over a matroid|
|Affiliation:||Member, School of Mathematics|
|Date:||Tuesday, October 7|
|Time/Room:||10:30am - 12:30pm/S-101|
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.