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.

Assignments and grading.

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)

Instructor notes:

Source materials: