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.