Abstract
The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Submodular functions are commonly used as utility functions in economics and algorithmic game theory, and they play a major role in combinatorial optimization.
In this talk, I will survey several approaches for maximizing submodular functions. In particular, I will show several recent results that are based on solving multilinear relaxations. These relaxations play the role of linear programming relaxations in linear optimization problems.