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)


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.


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)