CS 583: Approximation Algorithms, Spring 2026

Approximation 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 Information

Lectures: 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.
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.

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:

• Recommended textbooks:
  • The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011.
  • Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004.
• Chandra's working notes (will be updated periodically through the semester)
• Another useful book: Approximation Algorithms for NP-hard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1995.
• Iterative Methods in Combinatorial Optimization by Lau, Ravi and Singh.
• Geometric Approximation Algorithms by Sariel Har-Peled, American Mathematical Society, 2011
• A compendium of NP Optimization Problems
• Notes and slides from previous editions of the course: Fall 2021 (lecture videos), Spring 2018, Spring 2016, Fall 2013, Spring 2011, Spring 2009 and Fall 2006.
• Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (Motwani-Raghavan), The Probabilistic Method (Alon-Spencer)
• Lecture notes from various places: CMU (Gupta-Ravi), CMU2 (Gupta), EPFL (Svensson).
• Jeff Erickson's algorithms lecture notes, old homeworks and exams
• Notes and pointers to topics in combinatorial optimization from Chandra's course in Spring 2010

Ed (sign up at link), Gradescope (YBRVG8)  

• Homework 0: Given 01/20/26, Due 01/27/26
• Homework 1: Given 01/29/26, Due 02/12/26
• Homework 2: Given 02/13/26, Due 02/27/26

Lectures (Tentative Schedule)

• Lecture 1: 01/20/2026, Introduction, Covering problems, Greedy for Set Cover
  • Chapters 1 and 2 in working notes
  • Chapter 1 in Williamson-Shmoys book
  • Chapters 1, 2 in Vazirani book
• Lecture 2: 01/22/2026, LP based algorithms for Vertex Cover, Set Cover
  • Chapters 1 and 2 in working notes
  • Chapter 1 in Williamson-Shmoys book
  • Chapters 1, 2 in Vazirani book
• Lecture 3: 01/27/2026, Finish LP based algorithms for Vertex Cover, Greedy for Set Cover via LP, Introduce Submodularity
  • Chapters 1 and 2 in working notes
  • Chapter 1 in Williamson-Shmoys book
  • Chapters 1, 2 in Vazirani book
• Lecture 4: 01/29/2026, Knapsack: Greedy, PTAS, FPTAS
  • Chapter 3 in working notes
  • Chapter 3 in Williamson-Shmoys book
  • Chapter 8 in Vazirani book
• Lecture 5: 02/03/2026, Maximum Weight Independent Set in Elimination Graphs
  • Chapter 4 in working notes
  • Ye-Borodin paper on elimination graphs
  • Kammer-Tholey paper on intersection graphs
• Lecture 6: 02/05/2026, Randomized rounding plus alteration for packing problems
  • Chapter 4 in working notes
• Lecture 7: 02/10/2026, Load Balancing, Bin Packing
  • Chapter 5 in working notes
  • Sections 2.3, 3.2 and 3.3, in Williamson-Shmoys book
  • Chapters 9, 10 in Vazirani book
• Lecture 8: 02/12/2026, Finish Bin Packing, Unrelated Machine Scheduling and Congestion Minimization via Randomized Rounding
  • Chapter 6, 7 in working notes
  • Section 5.11 in Williamson-Shmoys book
• Lecture 9: 02/17/2026, Generalized Assignment via Iterated Rounding
  • Chapter 6 in working notes
  • Chapter 3 in Iterative Methods in Combinatorial Optimization by Lau, Ravi and Singh.
• Lecture 10: 02/19/2026, (1-1/e) approximation for Max-GAP via Configuration LP
  • Chapter 6 in working notes
  • Paper of Fleischer, Goemans, Mirrokni and Sviridenko
  • Paper of Feige and Vondrak