UBC Submodularity and Optimization CPSC 536S, Winter term 1, 2026
Course Outline (updated sept 10, 2026)
Submodular set functions have played a central role in the development of combinatorial optimization and are sometimes viewed as the discrete analogue of convex functions. Submodularity has also been a traditional model in areas such as economics and supply chain management. More recently it has found interesting applications in other areas including machine learning and algorithmic game theory. These led to a huge amount of algorithmic work that continues to date.
We develop the basic properties of submodular functions and then present both classical methods and new algorithmic paradigms. We also emphasize applications, both old and from more recent literature. 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 applications to sensor placement, social welfare and community detection and densest subgraphs.
The course presents a number of fundamental optimization problems associated with submodular objective functions and constraints. As we present various model problems, we also propose an algorithm(s). In many cases we also establish a guaranteed approximation bound or an inapproximability bound (or both). Hence a reasonable mathematical background (say in linear algebra) is recommended.
Instructor
Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: This will be announced on piazza, but you are also welcome to email to set up an appointment at another time.
Lectures
Time: Tuesday and Thursday at 14:00 - 15:30 CEME 1212
Teaching Assistant
Joe Poremba Office hours: TBA
Grading
Course grade is based upon: 4 assignments (15% each), 3 short in-class quizzes (5% each), project (30%) and class participation (10%).
Quiz Dates
tentatively the last class day of September, October and November.
Reading
There is no course textbook. The following may be useful supporting material in optimization generally.
- Submodular Functions and Optimization, by Satoru Fujishige.
- Combinatorial Optimization; a polyhedral perspective, by A. Schrijver.
- Convex Optimization: Algorithms and Complexity, by S. Bubeck.
- Understanding and using linear programming, by Matou\u{s}ek and G\"artner.
- Linear Programming, by V. Chv\'atal.
- The theory of linear and integer programming}, by A. Schrijver.
- A course in convexity, by A. Barvinok.
- Numerical Optimization, by Nocedal and Wright.
- Convex optimization, by Boyd and Vandenberghe.
- For graph theory: Bondy and Murty
- Primer on Complexity Theory.
The course materials will be shared on Piazza. Assignments will be graded on Gradescope.
This is the 4th time this course is being taught and the content changes but the core ideas are always covered. Some previous versions covered DR-Submodularity, One-sided smoothness and Continuous Submodularity and another covered the Fujishige-Wolfe Algorithm. There are also new topics since last teaching such as chasing submodularity and poission processes for maximization. If there is a specific topic of interest, let me know. Or they are also available to you for the course project as well.