Submodular functions

In this talk we will give an overview of various aspects of submodular set functions. Several examples of submodular functions will be presented, including modular functions, polymatroid functions, and objective functions of various optimization problems, for example those related to facility location problems and to cuts in graphs.

The problem of minimization and maximization of submodular functions, and the submodular set cover problem will be discussed. Two approximation algorithms will be described: one for the problem of maximizing a given submodular function under a cardinality constraint due to Nemauser et al. and one for the unconstrained submodular maximization due to Buchbinder et al. More precisely, we will present a greedy algorithm for maximizing a submodular function under a cardinality constraint, one deterministic algorithm and two randomized algorithms with approximation factors 1/3, 1/4 and 1/2, respectively, for solving the uncostrained submodular maximization problem.

Finally, a new proof of the theorem due to Boros et al. stating that every hypergraph has an exact polymatroid separator will be given.