**This page:** http://math.mit.edu/18433

**When and where: **
The class meets on Mondays and Wednesdays from 1PM to 2:30PM in room E17-133. ** There will be two makeup lectures on Tuesdays April 7th and April 14th from 4:30PM to 6:00PM in room E17-122. **

**Instructor:** Michel Goemans, room
E17-322. **Office hours:** Tue 1:45PM-2:45PM.

**TA:** Chiheon Kim, chiheonk@math.mit.edu. Office hour on Thursday from 4:15PM to 5:15PM in E17-401N.

**Prerequisites:** Linear algebra. Exposure to discrete
mathematics (18.310) is a plus, as well as exposure to algorithms
(6.006 and/or 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.

**Assignments and grading.** There will be roughly
bi-weekly problem sets, an in-class quiz ** on Monday April 6th** and a final during final week.
Problem sets are due in class at the beginning of the lecture.
The grade will be 30% Psets, 30% quiz and 40%
final. Attendance is strongly encouraged. Graduate students and
undergraduates may be graded differently. **Late
policy.** Late problem sets will generally not be
accepted. For a 10% discount, you can send it up to 24 hours late as a pdf attachment to the lecturer goemans@math.mit.edu.

** Problem Sets:**

- Problem set 1 due in lecture on 2/18/2015.
- Problem set 2 due in lecture on 3/9/2015.
- Problem set 3 due in lecture on 3/30/2015.
- Problem set 4 due in lecture on 4/6/2015.
- Problem set 5 due in lecture on 4/22/2015.
- Problem set 6 due in lecture on 5/6/2015.

**Handouts:**

- Matching example
- Lecture notes on bipartite matching
- Lecture notes on non-bipartite matching
- Lecture notes on polyhedral theory and linear programming
- Lecture notes on flows and cuts
- Lecture notes on matroids
- Lecture notes on matroid intersection
- Lecture notes on the ellipsoid algorithm
- Chapter on the traveling salesman problem from Cook et al.
- Link to the Concorde app for TSP (on iphones/ipads)

**Syllabus:** (preliminary version)

- 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.