Graduate course – Submodularity

[Question Set 1] Submodular functions: Definitions, examples and mathematical

[Question Set 2] Matroids, submodular functions and polyhedral theory

[Question Set 3] Minimization of submodular functions

[Question Set 4] Maximization of submodular functions

[Question Set 5] Submodularity and randomness

Class Videos (can be downloaded from)

Reference Books

A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume A,B,C. 2003. Springer-Verlag.

S. Fujishige. Submodular Functions and Optimization, 2nd Edition, Volume 58, 2005. Elsevier

M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics, 2nd edition, 1993. Springer-Verlag.

G. L. Nemhauser, L. A. Wolsey. Integer and Combinatorial Optimization. 1999. Wiley

D.M Topkis. Supermodularity and Complementarity. 1998. Princeton University Press

F. Bach. Learning with submodular functions: A convex optimization perspective. 2013. Foundations and Trends in Machine Learning 6 (2-3), 145-373

K. Murota. Discrete Convex Analysis. 2003. SIAM.

Reference Articles

L. Lovasz. Submodular functions and convexity.1983. Mathematical Programming: The State of Art. 235-257.

G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. 1978. Mathematical Programming. volume 14, 265-294.

F. Bach. Submodular functions: from discrete to continuous domains. 2019. Mathematical Programming. volume 175, 419-459

Reference Courses

Jeff Bilmes: Submodular Functions, Optimization, and Applications to Machine Learning

Michel Goemans. Advanced Combinatorial Optimization

J. Vondrak. Polyhedral techniques in combinatorial optimization