Combinatorial Optimization

Description

 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.

Details

 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)

Announcements
  • 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 lecture room.

    Syllabus

     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, Matroid Duality
  • 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 Function Minimization
  • 21 February, 2011 Lecture 12: Ellipsoid, Polar Polytopes
  • 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 Chekuri, Kamal Jain, and Jan Vondrak.

    Exercises

    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.

    Reading Projects

    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 al..
  • 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 Yannakakis.
  • 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 Algorithmic Mechanism 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 reading: Truthful 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.