CS 583: Approximation Algorithms
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.
Instructor: Chandra Chekuri, 3228
Teaching Assistant: Nirman Kumar, 3240
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.
Tentative Topic List:
Note: The above list is tentative. Not all of the material can be covered in one semester.
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.
Lecture 1: 8/28/2013, Introduction and covering problems (vertex cover, dominating set, set cover)
Lecture 2: 8/30/2013, Analyis of Greedy for set cover, LP rounding for vertex cover, set cover
Lecture 3: 9/6/2013, Set Cover via dual fitting, Packing problems: Max Indep Set, Knapsack
Lecture 4: 9/4/2013, PTAS and FPTAS for Knapsack
Lecture 5: 9/11/2013 Multiprocessor Scheduling: 2-approximation and hardness
Lecture 6: 9/13/2013 PTAS for Multiprocessor Scheduling, Greedy and APTAS for Bin Packing
Lecture 7: 9/18/2013 Local search for Max-Cut, Submodular function maximization
Lecture 8: 9/20/2013 Finish local search for Submodular function maximization. Local search for bounded-degree spanning tree.
Lecture 9: 9/25/2013 Finish bounded-degree spanning tree. 2-approximation for k-center, mention local-search for k-median and approximation bound.
Lecture 10: 9/27/2013 LP background for approximation
Lecture 11: 10/02/2013 Randomized rounding for congestion minimization
Lecture 12: 10/04/2013 Start Network Design: Steiner tree, Metric-TSP
Lecture 13: 10/09/2013 Primal-dual for Vertex Cover and then on to Steiner Forest
Lecture 14: 10/11/2013 Finish Primal-dual for Steiner Forest
Lecture 15: 10/16/2013 Steiner Network, Augmentation Framework, Abstract Network Design
Lecture 16: 10/18/2013 Finish primal-dual for skew-supermodular functions
Lecture 17: 10/23/2013 Iterated rounding for Steiner Network
Lecture 18: 10/25/2013 Finish Iterated rounding for Steiner Network
Lecture 19: 10/30/2013 Intro to graph cut and partitioning problems and metric methods: multiway cut
Lecture 20: 11/01/2013 3/2-approximation for multiway cut and symmetric submodular multiway partition
Lecture 21: 11/06/2013 Multicut
Lecture 22: 11/08/2013 Sparsest cut via Multicut
Lecture 23: 11/13/2013 Intro to metric embeddings and Sparsest cut via l_1 embedding
Lecture 24: 11/15/2013 Probabalistic Tree Embeddings
Lecture 25: 11/20/2013 Intro to SDP and application to Max-Cut
Lecture 26: 11/22/2013 SDP for Coloring
Lecture 27: 12/03/2013 Finish SDP for Coloring, mention SDP for Sparsest Cut
Lecture 28: 12/05/2013 Hardness of approximation
Course Project Information