Combinatorial Optimization Reading Group - Chaitanya Swamy

Title: Submodular function maximization

Abstract:

I will give the introductory talk for this term's topic for the Combinatorial-Optimization Reading group, namely submodular function maximization. Submodular functions arise in diverse contexts in combinatorial optimization. Two prominent examples are cut functions of graphs and directed graphs, and coverage functions, and the problem of maximizing a submodular function generalizes various classical combinatorial-optimization problems such as the max-cut problem, and the maximum coverage problem. Consequently, there has been a great deal of interest in understanding submodular-function maximization. While this is an NP-hard problem, it turns out that submodular functions share a unique mix of concavity and convexity properties that can be leveraged to develop a rich toolkit of techniques to approach this problem, both in the unconstrained setting, and in constrained settings.

In this talk, I will give an overview of the most common models that have been looked at, giving some pointers to the main results, and discuss some of the underlying results and techniques in more detail.