Modern Aspects of Submodularity

Other Talks
Monday, March 19, 2012 - 09:20
8 hours (full day)
Klaus 1116
ETH, University of Tokyo, and IBM
Workshop Theme: 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 workshop will be held from March 19-22, 2012. For complete details and workshop program, please see the website.