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).
Additional references: (roughly in increasing difficulty level or comprehensiveness)