Jan Vondrak - Submodular Functions and Their Applications

Jan Vondrak from IBM Almaden presents as part of the UBC Department of Computer Science's Distinguished Lecture Series, November 15, 2012.

Submodular functions, a discrete analogue of convex functions, have played a fundamental role in combinatorial optimization since the 1970s. In the last decade, there has been renewed interest in submodular functions due to their interpretation as valuation functions of self-interested agents in algorithmic game theory. These developments have led to new questions as well as new algorithmic techniques.

In this talk, we will discuss the concept of submodularity, its motivation and its unifying role in combinatorial optimization, as well as the evolution of the relevant algorithmic techniques. We will survey the state of the art in optimization of submodular functions, as well as selected applications in algorithmic game theory, social networks and machine learning, and some future challenges.