Submodular functions and their applications - DLS Talk by Jan Vondrak, IBM Almaden Research Center

Speaker:  Jan Vondrak, IBM Almaden Research Center

Title:  Submodular Functions and Their Applications

Abstract:

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.

Bio:

Jan Vondrak received his PhD in applied mathematics from MIT in 2005, and a PhD in computer science from Charles University in 2007. He spent 1 year as a postdoctoral researcher at Microsoft Research, Redmond (2005-06), and 3 years as a postdoctoral fellow at Princeton University (2006-09). Since 2009, he has been a research staff member in the theory group at IBM Almaden Research Center.