Fall 2015 Seminar Series

DATE: 11/5/15
LOCATION: E51-315
TIME: 4:15pm
Reception immediately following

SPEAKER:
Jan Vondrak

TITLE
Algorithms for Optimization of Submodular Functions

ABSTRACT
Submodular functions appear in many areas of research, ranging from algorithmic game theory to maching learning and information theory. I will survey some of my work in this area, in particular algorithms based on the continuous relaxations that have proved useful for problems involving submodular functions - the multilinear relaxation and the Lovasz relaxation. Particular applications include welfare maximization in combinatorial auctions, sensor placement and image segmentation. I will also discuss some recent work whose goal is to make the algorithms more efficient.