CS 583/IE 519: Combinatorial Optimization, Spring 2022


Course Summary

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.


Administrative Information

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.
Counseling Center: 217-333-3704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801
University wellness center
Please do not hesitate to contact the instructor if you need help or assistance.

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

References

Electronic 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)  


Homework

Lectures

  • Lecture 1: 1/18/2022, Introduction
    • Chapter 1 of notes
    • Preface of Schrijver's book
  • Lecture 2: 1/20/2022, Non-bipartite matching, Tutte-Berge formula and Edmonds algorithm for max cardinality matching
    • Chapter 2 of notes and references
  • Lecture 3: 1/25/2022, Basics of Polyhedra and LP
    • Chapter 3of notes
    • Schrijver's book on linear and integer programming
  • Lecture 4: 1/27/2022, Continue previous topic