18.433 Combinatorial Optimization

When and where: The class meets on Tuesdays and Thursdays from 1PM to 2:30PM in room 2-105.

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

TA: Karola Meszaros. E-mail: karola@math. Office hours: Mon 12-1 in 2-334.

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 (6.006 and/or 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 (most likely on April 7th) and a final during final week (May 16th from 1:30PM to 4:30PM in Walker Memorial (W30)). 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.

Problem Sets

• Problem Set 1, due in class on Tuesday Feb 15th. Read the bipartite matching notes. From these notes, solve exercises 1-4, 1-5, 1-6, 1-8, 1-12. If you are a graduate student also do 1-17.
• Problem set 2, due in class on Tuesday March 1st.
• Problem set 3, due in class on Tuesday March 15th.
• Problem set 4, due in class on Tuesday March 29th.
• Solution to 4-12
• Problem set 5, due in class on Thursday April 21st.
• Problem set 6, due in class on Thursday April 28th.

Quiz There is a quiz in class on April 7th. Here is a sample quiz from 2 years ago.

Final from 2009 Here is a sample final from 2009. Caveat: it may not be representative from this year's final...

Updated course notes for 2011

• Lecture notes on bipartite matchings.
• Lecture notes on non-bipartite matchings.
• Lecture notes on linear programming and polyhedral combinatorics. Slightly updated on 3/17/2011.
• Lecture notes on matroids. (Some additional material on spans will be added.)
• Lecture notes on matroid intersection.

Course notes from 2009 (to be revised)

• Lecture notes on the ellipsoid algorithm.
• Lecture notes on flows and cuts.