Combinatorial Optimization Reading Group - Justin Toth

Title: Maximizing a Monotone Submodular Function subject to a Matroid Constraint

Abstract:

Based on the paper by Calinescu, Chekuri, Pál, and Vondrák of the same title. We will study a randomized $(1-\frac{1}{e})$-approximation algorithm for the titular problem. To achieve the result three main techniques were needed: the multilinear extension, the continuous greedy algorithm, and pipage rounding. We will discuss each technique in turn and see how they come together to give the desired approximation algorithm.