18.433 Combinatorial Optimization

When and where: The class meets on Tuesdays and Thursdays from 11AM to 12:30PM in room 4-149.

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

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

Quiz: There will be an in-class quiz on Thursday April 11th. Here is a sample quiz from a previous year (given just for your information).

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, 2012. Available online with MIT certificates.
• 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency , Springer-Verlag, 2003.

Syllabus: (preliminary version)

• 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 traveling salesman problem.

Assignments and grading. There will be roughly bi-weekly problem sets, an in-class quiz scheduled for Thursday April 11 and a final during final week. 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.

Homework:

• Problem set 1 due in class on Thursday Feb 21st, 2013. From the notes on bipartite matchings, solve exercises 1-2, 1-3, 1-4, 1-5 and 1-12. Graduate students also do 1-8.
• Problem set 2 due on Tuesday March 5th in class. From the notes on non-bipartite matchings, solve 2-1, 2-2 and 2-3. From the notes on linear programming and polyhedral combinatorics, solve 3-1, 3-2. Graduate students: also solve 2-7.
• Problem set 3 due in class on Tuesday April 2nd. From the notes on polyhedral combinatorics, solve exercises 3-9, 3-12 and 3-17. From the notes on matroids, solve exercises 4-2, 4-7 and 4-8.
• Problem set 4 due in class on Thursday April 25th, 2013.
• Problem set 5 due in class on Thursday May 9th, 2013.

Handouts:

• Lecture on 2/5/2013: matching example, spanning tree game and Concorde TSP iphone/ipad app.

Course notes:

• Lecture notes on bipartite matchings.
• Lecture notes on non-bipartite matchings.
• Lecture notes on linear programming and polyhedral combinatorics.
• Lecture notes on matroids.

Course notes from earlier terms that will be slightly updated:

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