**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) | |