Computer Science Department

CS 583: Approximation Algorithms

Chandra Chekuri

Fall 2013

Course Summary

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. A rich algorithmic theory has been developed in this area and deep connections to several areas in mathematics have been forged. The first third to half of the course will provide a broad introduction to results and techniques in this area with an emphasis on fundamental problems and widely applicable tools. The second half of the course will focus on more advanced and specialized topics.

Administrative Information

Lectures: Wed, Fri 11:00am-12.15pm in Siebel Center 1302.

Instructor:  Chandra Chekuri, 3228 Siebel Center, chekuri at illinois

Teaching Assistant:  Nirman Kumar, 3240 Siebel Center, nkumar5 at illinois

Office Hours (Chandra): Monday 11am-noon

Office Hours (Nirman): Friday 3-4 PM

Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 4. Students can either choose to do the two or do a course project (more information on topics forthcoming). Course projects could involve research on a specific problem or topic, a survey of several papers on a topic (summarized in a report and/or talk), or an application of approximation algorithms to some applied area of interest including experimental evaluation of specific algorithms.

Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Officially the prerequisite is CS 573 or equivalent. Knowledge and exposure to probability and linear programming is necessary. The instructor will try to make the material accessible to non-theory students who might be interested in applications. Consult the instructor if you have questions.

Study material:

Tentative Topic List:


Note: The above list is tentative. Not all of the material can be covered in one semester.


Piazza signup

Moodle site


Homework 0 (tex file) given on 08/28/2013, due in class on Friday 09/06/2013.

Homework 1 (tex file) given on 09/06/2013, due on Friday 09/20/2013.

Homework 2 (tex file) given on 09/21/2013, due on Monday 10/07/2013.

Homework 3 (tex file) given on 10/05/2013, due on Monday 10/21/2013.

Homework 4 (tex file) given on 10/21/2013, due on Monday 11/04/2013.

Homework 5 (tex file) given on 11/04/2013, due on Friday 11/22/2013.

Homework 6 (tex file) given on 11/22/2013, due on Monday 12/09/2013.


Warning: Notes may contain errors. Please bring those to the attention of the instructor.


Course Project Information