18.453 Combinatorial Optimization (SPRING 2017)

This page: http://math.mit.edu/18453

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

Instructor: Michel Goemans, room 2-474.

Office hours: Wed 2:30PM-3:30PM in 2-474.

TA: Chiheon Kim, 2-390D, office hour: Tu 4PM-5PM.

Prerequisites: Linear algebra. Exposure to discrete mathematics (18.200) is a plus, as well as exposure to algorithms (6.006 and 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.

Assignments and grading. There will be roughly bi-weekly problem sets, an in-class quiz on Tue April 11th and a final on Thu May 25th from 1:30PM to 4:30PM in 4-237. There might be additional questions on psets for graduate students. Problem sets are due in class at the beginning of the lecture. 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. For a 10% discount, you can send it up to 24 hours late as a pdf attachment to the lecturer goemans@math.mit.edu.

There weren't lectures on 4/25 and 4/27/2017. There were makeup lectures on Wednesday 4/19/2017 at 6PM in 2-361 and on Monday 3/20/2017 at 7PM in room 2-449. Please check back for the scheduling of other makeup lectures.

Problem Sets:

• Problem set 1, due 2/23/2017.
• Problem set 2, due 3/9/2017.
• Problem set 3, due 3/23/2017.
• Problem set 4, due 4/6/2017 (or 4/9 electronically).
• Problem set 5, due 5/11/2017.

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.

Handouts:

• From Lecture 1 on 2/7/2017:
  • Matching instance
  • Spanning tree game
  • Spin glass instance
• Lecture notes on bipartite matching
• Lecture notes on maximum matchings in general graphs
• Lecture notes on linear programming and polyhedral combinatorics (proof of matching polytope added.)
• Lecture notes on maximum flows and minimum cut problems (updated with a new section 4.3.1.)
• Lecture notes on matroids
• Lecture notes on matroid intersection
• Lecture notes on the ellipsoid algorithm
• Chapter on the traveling salesman problem from W. Cook et al.
• Link to the Concorde app for TSP (on iphones/ipads), developed by W. Cook.