Hauptseminar (S2C2): Submodular function maximization

Submodular set functions appear across various areas such as combinatorial optimization, machine learning, information theory, and mathematical economics. While submodular function minimization admits polynomial-time algorithms, submodular maximization is NP-hard already in the unconstrained setting. Maximizing submodular functions subject to cardinality, knapsack, and matroid constraints is used in a wide range of applications.

Starting from the analysis of the greedy algorithm in the 1970s, the last two decades have seen exciting developments in new algorithmic techniques for approximating submodular function maximization in various settings, obtaining tight results in many cases. These include new variants of the greedy algorithm, new mathematical programming relaxations, the development of the continuous greedy algorithm, new rounding algorithms and local search algorithms, as well as lower bounds and hardness results. The course will also include applications to allocation, routing, and orienteering problems.

These developments have been summarised in the upcoming book Maximizing Submodular Set Functions by Chandra Chekuri and Jan Vondrák. You can find the table of contents here. The course will cover selected chapters of this book.

You can find the slides from the planning meeting here.