CS 583: Approximation Algorithms, Spring 2026Approximation algorithms for NP-hard problems are polynomial time heuristics that have guarantees on the quality of their solutions. Such algorithms are one robust way to cope with intractable problems that arise in many areas of Computer Science and beyond. In addition to being directly useful in applications, approximation algorithms allow us to explore the structure of NP-hard problems and distinguish between different levels of difficulty that these problems exhibit in theory and practice. The course will have a mix of basic and advanced topics and a range of problems. Administrative InformationLectures: Tue/Thu 12.30 to 1.45pm, 106B8 Engineering Hall.Instructor: Chandra Chekuri, 3228 Siebel Center, (chekuri at) Office Hours: 1-2pm on Fridays in 3228 Siebel (Chandra's office) Attendance policy: at least 65% of lectures for a grade. Grading Policy: 5 home works (60%), 1 mid term exam (20%), final project (20%) Prerequisites: Graduate level class; background in algorithms (CS 473 or equivalent) and discrete mathematics is needed. Knowledge of probability and linear programming is necessary. 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. Student code: All students are expected to be aware of the university's student code, in particular the academic integrity policies CS Code of Conduct: See here for important information on the code of conduct guidelines of the Siebel School of CS. Study material:
Ed (sign up at link), Gradescope (YBRVG8)Homework
Lectures (Tentative Schedule)
|