This graduate-level course covers advanced topics in combinatorial
optimization including non-bipartite matchings, polytopes, submodular
function minimization, and matroids. The emphasis is on the
derivation of purely combinatorial results and involves a deep
understanding of the underlying combinatorial structures. Lectures
will be highly interactive, and students are expected to help others
master the material with in-class explanations of difficult concepts
in a group-learning environment.
Lectures: M 3-4.30, Kellogg 586; W 12.30-2, Tech L158
Professor: Nicole Immorlica
Email: nickle at eecs dot northwestern dot edu
Office Hours: by appointment, Ford 3.327
Textbook: Combinatorial Optimization: Polyhedra and Efficiency, by Lex Schrijver
Grading: based on exercises and reading projects (see below)
Students are now expected to do 10 (not 15) exercises.
Class is canceled on Monday, January 24th.
Class is canceled on Wednesday, January 12th. There will instead
be a lecture on MLK day, Monday, January 17th, in our regular Monday
Note: The course is based on the course Advanced
Combinatorial Optimization by Michel Goemans. Students may find
it useful to supplement their reading with his lecture notes. I am
also posting the notes that I teach from. These are in no way
guaranteed to be correct or even comprehensible, but nonetheless
students may find them useful as a supplement to their own notes.
3 January, 2011. Lecture 1: Bipartite matching -- Konig's Theorem
5 January, 2011. Lecture 2: Non-bipartite
matching -- Tutte-Berge Formula, Edmonds' Algorithm
10 January, 2011. Lecture 3: Non-bipartite
matching -- Edmonds-Gallai Decomposition
17 January, 2011 Lecture 4: Edmonds-Gallai
Decomposition, Matching Polytope, Total Dual Integrality (TDI)
19 January, 2011 Lecture 5: TDI, Cunningham-Marsh
26 January, 2011 Lecture 6: Matroids,
31 January, 2011 Lecture 7: Matroid
Representation, Matroid Optimization
7 February, 2011 Lecture 8: Matroid
Intersection, Theorem Statement and Applications
9 February, 2011 Lecture 9: Matroid
Intersection, Inductive Proof of Min-Max Relation
14 February, 2011 Lecture 10: Matroid
Intersection, Algorithmic Proof of Min-Max Relation
16 February, 2011 Lecture 11: Submodular
21 February, 2011 Lecture 12: Ellipsoid,
28 February, 2011 Lecture 13:
Matroid Union, Base Packing (Aleck Johnsen)
2 March, 2011 Lecture 14: Black-box mechanism design (Nima
Haghpanah and Manolis Pountourakis)
7 March, 2011 Lecture 15: Shannon
switching game (Darrell Hoy and Greg Stoddard)
9 March, 2011 Lecture 16: Matroid
representation (Greg McGlynn)
Other similar courses include those by Chandra
Jain, and Jan
Students are expected to complete 10 problems from among these exercises (to be updated as the quarter
proceeds). In the spirit of group learning, students are encouraged
to propose problems to be included in the list of exercises.
Students are expected to complete a reading project which can be from
among those posted below (to be updated as the quarter proceeds)
Reading projects should be done in groups of at most two students
and will culminate in a 45 minute presentation per student as well as a written
summary of 3-5 pages.
The use of Edmonds-Gallai decompositions in network exchange
theory. Recommended reading: Balanced
Outcomes in Social Exchange Networks by Kleinberg and Tardos, Convergence
of Local Dynamics to Balanced Outcomes in Exchange Networks by
Azar et al., and A
Natural Dynamics for Bargaining on Exchange Networks by Bayati et
Dealing with the exponential size of the matching polytope.
Recommend reading: Odd
Minimum Cut-Sets and $b$-Matchings by Padberg and Rao, and Expressing
Combinatorial Optimization Problems by Linear Programs by
Online and stochastic algorithms for matroid optimization.
Recommended reading: Matroids,
Secretary Problems, and Online Mechanisms by Babaioff et al.; Multi-parameter Mechanism Design and Sequential
Posted Pricing by Chawla et al.; Matroid Secretary
Problem in the Random Assignment Model by Soto; and the
Design lecture notes of Jason Hartline, sections 6.5.6-6.5.9
(available upon request).
Submodular function maximization. Recommended reading: Maximizing
a Submodular Set Function subject to a Matroid Constraint by
Calinescu et al.; Maximizing non-monotone submodular
functions by Feige et al.
Polyhedra in design of maximal-in-range mechanism. Recommended
and Near-Optimal Mechanism Design via Linear Programming by Lavi
and Swamy; From Convex Optimization to Randomized
Mechanisms: Toward Optimal Combinatorial Auctions for Submodular
Bidders by Dughmi et al. (available upon request).
Shannon's switching game. Recommended reading: Lectures 13 and
14 from Goemans' course; A solution to Shannon's switching game by Lehman.
You may also simply lecture on a (cohesive) topic covered in one of
the related courses that was not covered in our course, or you may
propose your own topic. Make sure the topic is substantial enough to
fill a 1.5 hr lecture (or 45 minutes if you are doing the project alone), but not overly ambitious. Assume NOTHING from
your audience beyond what was taught in this course.