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: Vivek Madan, 3240
Office Hours (Chandra): Tuesday, 1.30 - 2.30pm in 3228 Siebel
Office Hours (Vivek): Monday, 3 - 4pm in Siebel 3rd floor lounge
Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 4. Students have the option of doing a course project in lieu of the last two homeworks (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 (now Theory II) 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 01/20/2016, due in class on Friday 01/29/2016.
Homework 1 (tex file) given on 02/03/2016, due in class on Wednesday 02/17/2016.
Homework 2 (tex file) given on 02/17/2016, due in class on Wednesday 03/02/2016.
Homework 3 (tex file) given on 03/04/2016, due in class on Friday 03/18/2016.
Homework 4 (tex file) given on 03/28/2016, due in class on Friday 04/8/2016.
Homework 5 (tex file) given on 04/16/2016, due in class on Wednesday 04/27/2016.
Homework 6 (tex file) given on 04/27/2016, due on Monday 05/09/2016.
Warning: Notes may contain errors. Please bring those to the attention of the instructor.
Lecture 1: 1/20/2016, Introduction, Covering problems, Greedy for Set Cover
Lecture 2: 1/22/2016, LP rounding for vertex cover, set cover
Lecture 3: 1/27/2016, Dual-fitting analysis for Set Cover, Additive vs Relative approx, Dominating Set Hardness
Lecture 4: 1/29/2016, PTAS and FPTAS for Knapsack
Lecture 5: 2/3/2016, Packing problems: maximum independent set, packing integer programs
Lecture 6: 2/5/2016, Finish PIPs, Multiprocessor scheduling
Lecture 7: 2/10/2016, Multiprocessor scheduling: PTAS, precedence constraints, inapproximability
Lecture 8: 2/12/2016, Unrelated machine scheduling: randomized rounding and 2-approx
Lecture 9: 2/17/2016, Generalized assignment via iterated rounding, congestion minimization for routing
Lecture 10: 2/19/2016, Uncapacitated facility location: non-metric and metric
Lecture 11: 2/24/2016, Clustering problems: k-center, k-median, and related. Intro to local search.
Lecture 12: 2/26/2016, Local search for max-cut, submod-max, facility location, k-median.
Lecture 13: 3/2/2016, Finish previous lecture.
Lecture 14: 3/4/2016, Start Network Design, Steiner Tree, Metric TSP.
Lecture 15: 3/9/2016, ATSP, Intro to primal dual via vertex cover, feedback vertex set.
Lecture 16: 3/11/2016, Primal dual for Steiner tree/forest.
Lecture 17: 3/16/2016, Steiner Network, Augmentation Framework, Abstract Network Design.
Lecture 18: 3/18/2016, Covering skew-supermodular functions, iterated rounding approach of Jain.
Lecture 19: 3/30/2016, 2-approx for Steiner Network via iterated rounding.
Lecture 20: 4/1/2016, Finish counting argument for Steiner network iterated rounding. Intro to graph cut and partition problems.
Lecture 21: 4/6/2016, 2-approx for Multiway Cut: edge, node, directed.
Lecture 22: 4/8/2016, 1.5 approx for multiway cut.
Lecture 23: 4/13/2016, Multicut, O(log k) approximation/flow-cut gap, lower bound via expanders.
Lecture 24: 4/13/2016, Sparsest cut and O(log^2 k) approximation via Multicut.
Lecture 25: 4/20/2016, Intro to metric embeddings, Sparsest cut via l_1 embedding.
Lecture 26: 4/22/2016, Finish sparsest cut via l_1 embedding, probabilistic tree embeddings.
Lecture 27: 4/27/2016, Intro to SDP, Max-Cut.
Lecture 28: 4/29/2016, 3-Coloring via SDP.
Lecture 29: 5/4/2016, Hardness of approximation, closing thoughts.