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)
Syllabus:
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) | |