Talks
Fall 2017

Submodular Optimization

Wednesday, September 13th, 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.

AttachmentSize
PDF icon Submodular Optimization1.22 MB