Computer Science/Discrete Mathematics Seminar II

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.