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:
- 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
Homework
Project
- Guidelines
- Compilation of approximation papers from the last five years of top theory conferences (generated by Claude from a prompt so all the typical caveats apply)
- SODA 2026 papers, STOC 2026 accepted papers
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
- 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
- Lecture 11: 02/24/2026, k-center clustering, facility location via LP
- Chapter 9 in working notes
- Chapter 2 in Williamson-Shmoys book for k-center (Gonzalez's algorithm)
- Chapter 5 in Vazirani book for k-center (the bottleneck algorithm)
- Lecture 12: 02/26/2026, Primal dual for vertex cover and for facility location
- Chapter 9 in working notes
- Chapter 24 in Vazirani book on facility location
- Chapter 7 in Williamson-Shmoys book for intro to primal-dual and several examples
- Lecture 13: 03/03/2026, Finish primal dual for facility location, start local search via Max Cut
- Chapter 9 in working notes for facility location
- Chapter 9 in Williamson-Shmoys book for local search
- Chapter 8 in working notes for local search
- Lecture 14: 03/05/2026, Local search for k-median
- Midterm exam: 03/10/2026
- Lecture 15: 03/12/2026, Intro to cut and partition problems, Multiway Cut
- Chapters 14 and 15 in working notes
- Chapter 8 in Williamson-Shmoys book
- Chapter 19 in Vazirani book
- Lecture 16: 03/24/2026, 1.5 approx for Multiway Cut via CKR Relaxation
- Chapter 15 in working notes
- Chapter 8 in Williamson-Shmoys book (Sec 8.2)
- Chapter 19 in Vazirani book
- Remark: the notes give a slightly different algorithm/analysis compared to the ones in the book. Perspective from this paper.
- Lecture 17: 03/26/2026, Approximating Multicut via CKR Rounding
- Chapter 17 in working notes
- Chapter 8 in Williamson-Shmoys book
- Chapters 18 and 20 in Vazirani book
- Lecture 18: 03/31/2026, CKR Rounding as Low Diameter Decomposition
- Chapter 18 in working notes
- Chapters 4 on low-stretch spanning trees in Anupam Gupta's notes
- Chapter 8 in Williamson-Shmoys book. Do you know what the picture on the cover of the book represents?
- Lecture 19: 04/02/2026, Probabilistic tree embeddings for metrics
- Chapter 18 in working notes
- Chapters 4 on low-stretch spanning trees in Anupam Gupta's notes
- Lecture 20: 04/07/2026, Sparsest Cut: Intro and rounding via Multicut
- Chapter 19 in working notes
- Chapters 15 in Williamson-Shmoys book
- Chapters 21 in Vazirani book
- Lecture 21: 04/09/2026, Sparsest Cut via \ell_1 embeddings
- Chapter 19 in working notes
- Chapters 15 in Williamson-Shmoys book
- Chapters 21 in Vazirani book
- Lecture 22: 04/014/2026, Inro to SDP, Max-Cut via SDP
- Chapter 20 in working notes
- Chapter 6 in Williamson-Shmoys book
- Chapter 26 in Vazirani book
|