MIT 18.453 Combinatorial Optimization

研究生课程（内涵笔记、作业解答

）

Course information

Instructor: Michel Goemans, room 2-474.


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.
  

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