**When and where:
The class meets on Tuesdays and Thursdays from 11AM to 12:30PM in
room 4-149. **

**Instructor:** Michel Goemans, room
2-351. **Office hours:** Wed 2:45PM-3:45PM.

**This page:** http://math.mit.edu/~goemans/18433S13/18433.html

**Quiz:** There will be an in-class quiz on Thursday April 11th. Here is a sample quiz from a previous year (given just for your information).

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

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

**Assignments and grading.** There will be roughly
bi-weekly problem sets, an in-class quiz scheduled for Thursday April 11 and a final during final week.
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. Still, for a good reason, an arrangement can be made
provided you discuss it with the instructor at least 48 hours prior to
the deadline.

**Homework:**

- Problem set 1 due in class on Thursday Feb 21st, 2013. From the notes on bipartite matchings, solve exercises 1-2, 1-3, 1-4, 1-5 and 1-12. Graduate students also do 1-8.
- Problem set 2 due on Tuesday March 5th in class. From the notes on non-bipartite matchings, solve 2-1, 2-2 and 2-3. From the notes on linear programming and polyhedral combinatorics, solve 3-1, 3-2. Graduate students: also solve 2-7.
- Problem set 3 due in class on Tuesday April 2nd. From the notes on polyhedral combinatorics, solve exercises 3-9, 3-12 and 3-17. From the notes on matroids, solve exercises 4-2, 4-7 and 4-8.
- Problem set 4 due in class on Thursday April 25th, 2013.
**Problem set 5 due in class on Thursday May 9th, 2013.**

**Handouts:**

- Lecture on 2/5/2013: matching example, spanning tree game and Concorde TSP iphone/ipad app.

**Course notes:**

- Lecture notes on bipartite matchings.
- Lecture notes on non-bipartite matchings.
- Lecture notes on linear programming and polyhedral combinatorics.
- Lecture notes on matroids.

**Course notes from earlier terms that will be slightly updated:**