18.453 Combinatorial Optimization
When and where:
The class meets virtually Tuesdays and Thursdays from 11AM to 12:30PM using Zoom (Kerberos authentication required) . Lectures are recorded, but attendance is strongly encouraged. Apart from lecture, don't forget to join the course Slack through canvas! Thanks to the creators of abot for giving us free access to their anonymous poll Slack app.
Instructor: Cole Franks, room
2-241 (in non-pandemic times).
Office hours: Mon 6:30p-8p and Wed 11a-12p, or by appointment, via Zoom and/or explain.mit.edu. The room 2-147 is reserved 11a-12:30 Wed for on-campus students to meet if they wish.
TA: Alexey Balitskiy, Room 2-231A, office hour: 5:30-7 pm Thursday.
Prerequisites: Linear algebra. Exposure to discrete
mathematics (18.200) is a plus, as well as exposure to algorithms
(6.006 and 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.
For more on matroids, see the book "Matroid Theory" by Welsh or the (different) book "Matroid Theory" by Oxley.
Assignments and grading.
- Psets: There will be roughly
bi-weekly problem sets. Students will be grouped into teams to facilitate pset collaboration, but must write up their own work. There will be designated Zoom rooms and slack channels for psetting, and the course is also active on pset partners . There might be additional questions on psets for graduate students, and undergraduates can earn a small number of bonus points for completing these problems. Problem sets will be submitted through the Gradescope tool in Canvas. Graduate students and
undergraduates may be graded differently. When possible, psets will be due 11:00 pm Thursday nights.
- Quiz: There will be a timed quiz Thursday April 1 (replacing class).
- Final: There will be a timed final which can be started any time Monday, May 24 9:00a - Tuesday, May 25 9:00a but must be completed in 3 hours once opened.
Grade calculation: 40% psets (each weighted the same), 25% quiz, 35% final.
Late
policy: Late problem sets will generally not be
accepted. For a 10% discount, you can upload it to Canvas up to 24 hours late.
Honor code:
There is absolutely no consultation with one another, or anyone else, allowed during the quiz and final.
Problem Sets:
Hand these in using the Gradescope tool in Canvas. Please label your pages carefully.
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.
Instructor notes:
Source materials: