18.433 Combinatorial Optimization

When and where: The class meets on Mondays, Wednesdays and Fridays from 3PM to 4PM in room 2-131.

Instructor: Michel Goemans, room 2-351. Office hours: Tu 2-3PM.

TA: Hoda Bidkhori, room 2-586, bidkhori@mit.edu. Office hours: Thursday, 4-5PM.

This page: http://math.mit.edu/~goemans/18433.html

Prerequisites: Linear algebra. Exposure to discrete mathematics (18.310) is a plus, as well as exposure to algorithms (18.410).

Textbook: There is no required textbook. Lecture notes will be distributed during the term. For additional references, the following textbooks are recommended (roughly in increasing difficulty level or comprehensiveness). The last two are especially recommended to anyone interested in a recent, in-depth coverage of the subject.

• J. Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.
• W. Cook, W. Cunningham, W. Pulleyblank and A. Schrijver, Combinatorial Optimization.
• C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
• E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
• G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
• B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21 Springer, Berlin Heidelberg New York, 2006.
• 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.

Syllabus:

• Introduction.
• Cardinality bipartite matching.
• Efficiency of algorithms.
• Assignment problem.
• Non-bipartite matching.
• Polytopes, linear programming, geometry.
• Polyhedral combinatorics.
• Maximum flow problem.
• Minimum cut problems.
• The ellipsoid algorithm.
• The matching polytope.
• Matroids. Matroid optimization, matroid polytope.
• Matroid intersection.
• Arborescence problem.
• Matroid union.
• The travelling salesman problem.

Assignments and grading. There will be roughly bi-weekly problem sets, an in-class quiz on Wednesday April 8 and a final on May 19th from 9AM-12 noon in room 2-139. The grade will be 30% Psets, 30% quiz and 40% final. Attendance is strongly encouraged. Graduate students and undergraduates may be graded differently. Late policy. Late problem sets will generally not be accepted. Still, for a good reason, an arrangement can be made provided you discuss it with the instructor at least 48 hours prior to the deadline.

Handouts.

• Spanning tree game.
• Matching instance.
• Lecture notes on bipartite matchings. Cardinality and weighted versions (assignment problem). [Numbering slightly modified on 2/18/09.]
• Problem set 1. Due Wed Feb 18th, 2009.
• Lecture notes on non-bipartite matchings.
• Lecture notes on linear programming and polyhedral combinatorics. (Corrected on 2/24/09.)
• Problem set 2. Due Mon March 2nd, 2009.
• Problem set 3. Due Fri March 13th, 2009.
• Lecture notes on matroid. Revised 3/20/2009, 3PM.
• Problem set 4. Due Wed April 1st, 2009.
• Lecture notes on matroid intersection. Incomplete, posted 4/1/2009.
• Problem set 5. Due Mon April 13th, 2009.
• Sample quiz from 2007. This was, however a 90-minute quiz!
• Problem set 6. Due Mon April 27th, 2009. (question 3(c) slightly modified on 4/19 at 6PM)
• Lecture notes on the ellipsoid algorithm.
• Incomplete lecture notes on flows and cuts. (Version as of May 15th 9AM.)