Fall 2017

Submodular Optimization

Wednesday, Sep. 13, 2017 9:30 am10:30 am

Add to Calendar

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.

PDF icon Submodular Optimization1.22 MB