Math 597 / Comp 554 (Winter 2017). This course is an introduction to submodular optimization.
Math 597 / Comp 554. (Winter 2017)
Submodular set functions have played a central role in the development of combinatorial optimization and could be viewed as the discrete analogue of convex functions. Submodularity has also been a useful model in areas such as economics, supply chain management and recently algorithmic game theory and machine learning. There has been a huge amount of work recently in approximation algorithms for various constrained submodular optimization models arising in practice, perhaps most prominently the social welfare maximization problem. We develop the basic properties of submodular functions and then present both classical methods and recent trends. Topics include: algorithms for unconstrained submodular maximization and minimization, polymatroids, local greedy algorithms, multilinear extensions and pipage rounding, Lovasz Extension and convex minimization, matroid constraints, multi-agent optimization, and many applications. Most materials will be shared online at MyCourses. A list of lectures will be posted here later in Fall 2016.