PublicationsManuscripts

We survey several recent algorithmic results on submodular maximization:

• The greedy algorithm for monotone submodular maximization over uniform matroids.
• The continuous greedy algorithm for monotone submodular maximization over arbitrary matroids (Calinescu, Chekuri, Pál and Vondrák).
• The non-oblivious local search algorithm for monotone submodular maximization over arbitrary matroids (Filmus and Ward).
• Uncostrained non-monotone submodular maximization (Buchbinder, Feldman, Naor and Schwartz).

We also briefly survey some lower bounds:

• $1-1/e$ NP-hardness for maximum coverage (Feige).
• $1-1/e$ value oracle hardness for monotone submodular maximization over a uniform matroid (Nemhauser and Wolsey).
• $1/2$ value oracle hardness for unconstrained submodular maximization (Feige, Mirrokni and Vondrák).
• The symmetry gap method (Vondrák, Dobzinski and Vondrák).

This talk was given at the Toronto Student Seminar on 31/1/2013.