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, multiagent 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:3015:00 (ICICS X839) or email to set up an appointment.
Lectures
Time: Tuesday and Thursday at 15:3017:00 Hugh Dempster Paviliion 101
Teaching Assistant
Sikander Randhawa Office hours: Friday 11:3012: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 takehome 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.
 For graph theory: Bondy and Murty
 Primer on Complexity Theory.
What we've done so far...
Week 1.
Tuesday
Motivating Examples.
 Valuations and Pricing Optimization
 Cuts in Graphs. Minimum, Maximum and Sparsest Cuts.
 Submodular Welfare
Thursday
Understanding Submodulariy.
 How are submodular functions like concave/convex functions?
 Operations preserving submodularity.
Week 2.
Tuesday
Recognizing Submodulariy.
 Examples of Submodular Functions. Coverage functions, matroid rank functions, closure problems, facility location etc.
 Ring families, Intersecting and crossing families
 Submodularity in the Constraints
Thursday
Unconstrained Maximization.
 A Random Set is a 1/4Approximation!
Week 3.
Tuesday
Lower Bounds for Unconstrained SO.
 We show that (somewhat amazingly) the Random Set Algorithm is optimal amongst a class of "myopic" nonadaptive algorithms.
 We mention stronger 1/2 lower bounds in both the oracle model and complexity model (assuming NP \neq RP)
Thursday
Double Greedy Algroithm.
 We prove that this is an (optimal) 1/2approximation in expectation
Week 4.
Tuesday
Local Search.
 General discussion on neighbhourhood search. Examples where we dont know how to find local optima (max cut). Approximate Local Search.
 We show that a simple local search method is a 1/3approximation for unconstrained submodular maximization.
Thursday
Extensions of Set Functions (continued).
 We define Convex, Concave, Multilinear and Lovasz Extensions of a set function.
 Quiz.
Week 5.
Tuesday Feb. 4
The Lovasz Extension of a Set Function is Convex IFF the Set Function is Submodular
Thursday Feb. 6
Polymatroids
 Definitions of Polymatroids and Extended Polymatroids.
 Summary of some basic facts and theorems (without proof) from convexity theory.
 Basics of LP Duality and Complementary Slackness.
Week 6
Tuesday Feb. 11
 The Greedy Algorithm for Extended Polytmatroids
 Equivalence of Separation and Optimization
 Solving Unconstrained Submodular Minimization (via Ellipsoid and Extended Polymatroids)
Thursday Feb. 13
The Ellipsoid Algorithm
Week 7
Reading Week
Week 8
Tuesday Feb. 25
 Projected Subgradient Methods. Convergence results statements.
 Comparison of runtime results for PSD versus Ellipsoid. In Polytime (strong/weak), PseudoPoly, epsilonadditive model (quantum, regular)
Thursday Feb. 27
Constrained Submodular Minimization
 Minimization Subject to Ring Families
 Parity Families
 Congruency Constrained Families
Week 9
Tuesday March 3
 Polynomial Inapproximability of CardinalityConstrained Submodular Minimization
 Approximating Submodular Functions Everywhere. Learning a Submodular Function
Thursday March 5
 Further examples of Inapproximable Combinatorial Families
 Any good news? Submodular Node (Vertex) Cover)
 Blockers of UpwardsClosed Families
 BApproximation for BBounded Blockers.
 Matching Inapproximability Result for BUniform Hypergraph Node Cover.
Week 10
Tuesday March 10
Intro to Constrained Maximization
 Definition of Generic Greedy Algorithm.
 Bad Example for Greedy Applied to NonMonotone Functions
 Greedy is a (11/e)Approximation For Monotone Submodular Maximization Subject to Cardinality Constraint
 Some Matroid Theory. Exchange Lemma.
Thursday March 12
 Definition of Generic Greedy Algorithm.
 1/2Approx for Monotone Submodular Maximization Subject to Matroid Constraint
 Introduction to pSystems. Some examples.
 Tight (to constant factors) O(p)Approx for psystems
Week 11. Lectures Go Online.
Tuesday March 17
 Proof of the Partition Lemma Needed for NonMonotone Maximization Over psystem.
Thursday March 19
 The Submodular Welfare Problem (SWP)
 SWP Can be Reduced to Monotone Maximization over a Partition Matroid.
 Motivating the Multilinear Extension
 Evaluating the Multilinear Extension
Week 12
Tuesday March 24
 Anlaytic Results for Multilinear Extensions.
 The Continuous Greedy Algorithm
Thursday March 26
 Rounding with Submodular Objectives in Matroid Polytope
Week 13
Tuesday March 31
MultiAgent Submodular Optimization
 Submodular Welfare, Minimum Submodular Cost Allocation (MSCA)
 Applications to Multiway Cut, Metric Labelling and General Submodular kWay Partition
 O(log^2(n)) MA Gap for Monotone Minimization
 (11/e) Gap for Multivariate Maximization
 Other Partitioning Objectives: Submodular Fair Allocation, Submodular Load Balancing
Thursday April 2

Continuous Submodularity
Week 14
Tuesday April 7
 Applications of FrankWolfe or Combinatorial Algorithm for SFM or Projected Subgradient Methods for SFM