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.
For more on matroids, see the book "Matroid Theory" by Welsh or the (different) book "Matroid Theory" by Oxley.
- J. Lee, A
First Course in Combinatorial Optimization, Cambridge University
Cook, W. Cunningham, W. Pulleyblank and A. Schrijver,
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.
Optimization: Polyhedra and Efficiency , Springer-Verlag,
Assignments and grading.
Grade calculation: 40% psets (each weighted the same), 25% quiz, 35% final.
policy: Late problem sets will generally not be
accepted. For a 10% discount, you can upload it to Canvas up to 24 hours late.
There is absolutely no consultation with one another, or anyone else, allowed during the quiz and final.
- 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 (date TBD).
Hand these in using the Gradescope tool in Canvas. Please label your pages carefully.
Syllabus: (preliminary version)
- 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.
- Perfect graphs.
- Lecture 1: Introduction; matching, spanning trees, and spin glasses.
- Lecture 2: Cardinality bipartite matching; König's theorem.
- Lecture 3: Minimum weight matching; primal-dual algorithm.
- Lectures 4 and 5: Non-bipartite matching; Tutte-Berge Theorem and Edmonds' algorithm.
- Lecture 6: Polyhedra, Fourier-Motzkin elimination, Farkas' Lemma.
- Lecture 7: Linear programming duality.
- Lecture 8: Faces of polyhedra, Krein-Milman Theorem.
- Lecture 9: Minimal descriptions of polyhedra, local picture of vertices.
- Lecture 10: Caratheodory's Theorem, Total unimodularity.
- Lecture 11: Non-bipartite matching polytope.
- Lecture 12: Max-flow min-cut.
- Lecture 13: Edmonds-Karp algorithm, Global min-cut.
- Lecture 14: Stoer-Wagner algorithm, Min T-odd cut.
- Lecture 15: Matroid optimization.
- Lecture 16: Matroid polytope; primal-dual proof.
- Lecture 17: Matroid polytope; vertex integrality proof.
- Lecture 18-19: Matroid intersection; largest common independent set.