Bruce Shepherd

UBC Submodular Optimization CPSC 536S, Winter term 2, 2020

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 be more theoretically focused as opposed to numerical. Hence a reasonable mathematical background (say in linear algebra) is recommended.

Instructor

Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Wednesday 13:30-15:00 (ICICS X839) or email to set up an appointment.

Lectures

Time: Tuesday and Thursday at 15:30-17:00 Hugh Dempster Paviliion 101

Teaching Assistant

Sikander Randhawa Office hours: TBA

Grading

Course grades will be 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 Thursdays of January, February, March

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.

What we've done so far...

Week 1.

Week 2.