CS 583/IE 519: Combinatorial Optimization, Spring 2022
The course will cover a selection of topics in combinatorial optimization. The emphasis will be on polyhedral theory, structural results and their applications to designing algorithms. Specific topics to be covered include: matchings and their applications, connectivity properties of graphs, matroids and optimization including matroid intersection and union, submodular set functions and applications, arborescences and branchings, and basics of multi-flows.
Lectures: Tue, Thu 11-12.20pm in Siebel Center 0216. Zoom link for online lectures during first week. Requires you to log in via Illinois credentials for security purposes
Recordings: Mediaspace channel
Instructor: Chandra Chekuri, 3228 Siebel Center, (chekuri at)
Teaching Assistant: Calvin Beideman, (calvinb2 at)
Office Hours (Chandra): TBA
Office Hours (Calvin): Wednesday 4:00-5:00 PM link
Grading Policy: 50% homework, 30% exams (2 x 15%), 20% project.
Attendance policy: at least 60% of lectures for a grade.
Prerequisites: This is a graduate level class. Official prerequisites: familiarity with linear programs (IE 411 or equivalent), algorithms (CS 374 or equivalent), and graph theory (MATH 412 or equivalent). Most important is mathematical maturity and comfort with formal proofs and arguments and interest in the topic. Consult the instructor if you have questions.
Covid-19 and mental health support at UofI:
Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
College of Engineering Syllabus Statements: See here for important information and regulations regarding academic integrity, disability accommodations, FERPA rights, religious observances, and sexual misconduct reporting.
Anti-racism and inclusivity: Official statement. Be kind, respectful, and professional to everyone and expect the same from others.Department of Computer Science values and code of conduct and CS Cares Committee
ReferencesElectronic versions of several books from Cambridge University, Springer, Wiley and other publishers are available free to Univ of Illinois students via the library.
Piazza, Gradescope (YV6ZPR)