18.433 Combinatorial Optimization

For a more recent version of this class, click here

No class on Tuesday April 3rd. In-class quiz on Thursday April 5th. At the quiz, you can have one single-sided handwritten sheet of paper.

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: Tu 3-4PM.

TA: Jose Soto, room 2-333, x3-7826. Email: jsoto@math.mit.edu. Office hours: Thu, 11am-12:30PM.

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)

• 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 Thu April 5th and a final on May 21 from 1:30PM to 4:30PM in 5-134. On each problem set, there will be additional problems for graduate students taking the class (there will be optional for the undergraduates). The grade will be 30% Psets, 30% quiz and 40% final. Attendance is strongly encouraged. Graduate students and undergraduates may be graded differently.

Schedule:

date	topic	reading/handouts	ps
Feb. 6	Introduction	Matching example, spanning tree game
Feb. 8	Bipartite matchings (cardinality)	Lecture notes on bipartite matchings (updated)
Feb. 13	Efficiency of algorithms. Assignment problem.		PS1 out
Feb. 15	Assignment problem (weighted bip. matchings).
Feb. 22	Non-bipartite matchings (cardinality case).	Lecture notes on non-bipartite matchings	PS1 due
Feb. 27	Polyhedral theory and linear programming.	Lecture notes on polyhedral theory	PS2 out
March 1	Polyhedral theory and linear programming (cont'd).
March 6	Polyhedral Combinatorics		PS2 due
March 8	Polyhedral Combinatorics (cont'd)		PS3 out
March 13	Totally unimodular matrices. Matroids	Matroid chapter (in class)
March 15	Matroids (greedy algorithm, rank)
March 20	Matroids (circuits, polytope)		PS4 out. PS3 due
March 22	Matroid intersection (definition, examples)	Matroid intersection chapter (in class)
April 3	No class
April 5	Quiz 1		PS4 due
April 10	Matroid intersection (cardinality algorithm, minmax)
April 12	Matroid intersection (cont'd), min-cost arborescences		PS5 out
April 19	Min-cost arborescences	Arborescence notes	PS5 due
April 24	Matroid dual and matroid union	Matroid union notes	PS6 out
April 26	Maximum flows
May 1	Maximum flows, minimum cuts	Mincut notes	PS6 due
May 3	Ellipsoid algorithm	Ellipsoid and minimum T-odd cut notes (updated)
May 8	Ellipsoid algorithm (cont'd)
May 10	Minimum T-odd cuts
May 15	Matching polytope
May 17	Review	Practice final (from previous year)