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: Friday 11:30-12:30 (effective immediately. pls contact Sikander to set up online meetings. Updates on Piazza.)

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.

What we've done so far...

Week 1.

Tuesday

Motivating Examples.

Thursday

Understanding Submodulariy.

Week 2.

Tuesday

Recognizing Submodulariy.

Thursday

Unconstrained Maximization.

Week 3.

Tuesday

Lower Bounds for Unconstrained SO.

Thursday

Double Greedy Algroithm.

Week 4.

Tuesday

Local Search.

Thursday

Extensions of Set Functions (continued).

Week 5.

Tuesday Feb. 4

The Lovasz Extension of a Set Function is Convex IFF the Set Function is Submodular

Thursday Feb. 6

Polymatroids

Week 6

Tuesday Feb. 11

Thursday Feb. 13

The Ellipsoid Algorithm

Week 7

Reading Week

Week 8

Tuesday Feb. 25

Thursday Feb. 27

Constrained Submodular Minimization

Week 9

Tuesday March 3

Thursday March 5

Week 10

Tuesday March 10

Intro to Constrained Maximization

Thursday March 12

Week 11. Lectures Go Online.

Tuesday March 17

Thursday March 19

Week 12

Tuesday March 24

Thursday March 26

Week 13

Tuesday March 31

Multi-Agent Submodular Optimization

Thursday April 2

Week 14

Tuesday April 7