**When and where:
The class meets on Tuesdays and Thursdays from 11:00 to 12:30 in room
2-102. **

**Instructor:** Michel Goemans, room
2-351.

**Office hours:** Tu 2-3PM.

**TA:** Luis Rademacher, lrademac@math. Office hours on Wed from 3-4PM in 2-090.

**Textbook:** The textbook is: Jon Lee, A
First Course in Combinatorial Optimization, Cambridge University
Press, 2004. There will be also additional lecture notes distributed
for some of the lectures. There will be topics discussed in lectures
that are not covered in the book.

**Topics:** This subject covers combinatorial
optimization which deals with optimization problems defined on
discrete structures. Typical problems and models in this field that we
will be discussing include
matching problems (bipartite or non-bipartite, cardinality or
weighted), matroid problems (cardinality or weighted maximization of
bases in one matroid or in the intersection of two matroids), flow
problems (disjoint path, maximum flow, minimum-cost
flow problems), the traveling salesman problem, etc. We will be dealing
with both computationally easy problems and also computationally hard
(NP-hard) problems. Problems will be studied from different
viewpoints: combinatorial (min-max relation, etc), algorithmic and
polyhedral (derivation of linear programming formulations). For the
latter, a few lectures will be devoted to linear
programming. Although the course will be theoretical in nature,
applications of combinatorial optimization are plentiful and very
diverse: kidney
exchanges, major league
baseball scheduling, ...

**Assignments.** There will be approximately 7 problem sets, an
in-class quiz and a final on Friday Dec 16 from 1:30PM to 4:30PM in 2-132. The quiz is
scheduled for Thursday November 10 in class. The grade will be 30% Psets, 30%
quiz and 40% final. Attendance is strongly encouraged.

**Handouts and links (see also Schedule page).**

- Great site on the traveling
salesman problem, the prototypical combinatorial optimization
problem. The site has lots of information, including the
**optimum**solution of a 24,978 cities instance. - 9/8/2005: Matching illustration from lecture 1.
- 9/8/2005: Spanning tree game from lecture 1.
- 9/8/2005: Problem set 1 due September 15th, 2005.
- 9/13/2005: Lecture notes on bipartite matching.
- 9/22/2005: Problem set 2 due September 29th, 2005.
- 9/23/2005: Notes on non-bipartite matchings.
- 10/04/2005: Problem set 3 due October 13th, 2005.
- 10/6/2005: Notes on Polyhedral Combinatorics.
- 10/18/2005: Problem set 4 due October 27th, 2005.
- 11/7/2005: Notes on the minimum cost arborescence problem.
- 11/7/2005: Notes on matroid union.
- 11/17/2005: Notes on the minimum cut problem.
- 11/17/2005: Problem set 5 due November 29th, 2005.
- 12/1/2005: Problem set 6 due December 8th, 2005.
- 12/6/2005: Notes on the ellipsoid algorithm.

**Additional references: (roughly in increasing difficulty
level or comprehensiveness) **

- 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.
- 3-volume book by A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (published by Springer-Verlag)