Bruce Shepherd

UBC Submodular Optimization CPSC 536S, Winter term 1, 2023

Course Outline

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.

The course will present a number of fundamental optimization problems associated with submodular objective functions and constraints. For each model we either present an algorithm or an inapproximability bound (or both). The course is theoretically focused in that our objective is usually to give guarantees around the existence of good algorithms. Hence a reasonable mathematical background (say in linear algebra) is recommended.

Instructor

Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Thursday 14:00-15:00 (ICICS X839) or email to set up an appointment at another time.

Lectures

Time: Monday and Wednesday at 13:00-14:30 Ponderosa Commons 1011

Teaching Assistant

Abner Turkieltaub Office hours:

Grading

Course grade is tentatively based upon: 3 assignments (15% each), 3 quizzes (10% each), a take-home final exam (20%), and class participation! (5%).

Quiz Dates

all in class. 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.

What we've done so far...

Week 1.