Submodular functions are discrete analogues of convex functions, arising in various fields of computer science and operations research. Since the seminal work of Jack Edmonds (1970), submodularity has long been recognized as a common structure of many efficiently solvable combinatorial optimization problems. Recent algorithmic developments in the past decade include combinatorial strongly polynomial algorithm for minimization, constant factor approximation algorithms for maximization, and efficient methods for learning submodular functions. In addition, submodular functions find novel applications in combinatorial auctions, machine learning, and social networks. This workshop aims at providing a forum for researchers from a variety of backgrounds for exchanging results, ideas, and problems on submodular optimization and its applications. The first day will be devoted to tutorial-style lectures!
Videos of all the tutorial sessions:
- Andreas Krause, Submodular Function Optimization in Sensor and Social Networks
- Andreas Krause, Submodular Function Optimization in Sensor and Social Networks II
- Kazuo Murota, Introduction to Discrete Convex Analysis
- Kazuo Murota, Minimization and Maximization Algorithms in Discrete Convex Analysis
- Jan Vondrak, Optimization of Submodular Functions: Relaxations and Algorithms
- Jan Vondrak, Optimization of Submodular Functions: Hardness and Optimality