CS 598: 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
Office Hours: by appointment
Course mailing list: firstname.lastname@example.org. You can subscribe here.
Grading Policy: There will be 6 homeworks, roughly once every two weeks. I expect all students to do the first 3. Students can either choose to do the next three 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. I also expect students to scribe one lecture in latex.
Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Knowledge and exposure to probability and linear programming would be ideal. 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 given on 01/19/11, not to be graded.
Homework 1 given on Friday 01/28/11, due in class on Friday, 2/11/11.
Homework 2 given on Sunday 2/13/11, due in class on Friday, 2/25/11.
Homework 3 given on Wednesday 3/9/11, due in class on Wednesday, 3/30/11.
Homework 4 given on Wednesday 3/30/11, due in class on Wednesday, 4/13/11.
Homework 5 given on Friday 4/15/11, due in class on Friday, 4/29/11.
Homework 6 given on Friday 4/29/11, due 5/9/11.
Warning: Notes may contain errors. Please bring those to the attention of the instructor.
Lecture 1: 1/10/11, Introduction, Steiner trees (MST heuristic, Greedy).
Lecture 2: 1/21/11, The Traveling Salesperson Problem, NP Optimization problems.
Lecture 3: 1/26/11, Set Cover and Maximum Coverage via Greedy
Lecture 4: 1/28/11, Vertex Cover and Set Cover via Linear Programming
Lecture 5: 2/4/11, Set Cover via Dual-Fitting
Lecture 6: 2/9/11, Knapsack, PTAS and FPTAS
Lecture 7: 2/11/11, Maximum Independent Set, Packing Integer Programs
Lecture 8: 2/16/11, Continue previous lecture
Lecture 9: 2/18/11, Congestion minimization
Lecture 10 (by Alina Ene): 2/23/11, Unrelated Machine Scheduling
Lecture 11 (by Alina Ene): 2/25/11, Minimum-cost Generalized Assignment
Lecture 12: 3/2/11, Local Search for Max Cut and Submodular Function Maximization
Lecture 13: 3/4/11, Introduction to Clustering and Location Problems, k-Center
Lecture 14: 3/9/11, Local Search for k-median
Lecture 15: 3/11/11, Background on LP (ellipsoid method, equivalence of separation and optimization, integer polyhedra, primal-dual method), primal-dual for Vertex Cover
Lecture 16: 3/16/11, Primal-dual for Network Design (Steiner Forest)
Lecture 17: 3/18/11, Primal-dual for Network Design (0-1 Skew Supermodular)
Lecture 18: 3/30/11, Primal-dual for Network Design (0-1 Skew Supermodular)
Lecture 19: 4/1/11, Survivable Network Design Problem (Intro, 2k-approx, etc)
Lecture 20: 4/6/11, Iterated Rounding 2-approx for Survivable Network Design Problem
Lecture 21: 4/8/11, Intro to metric methods, Multiway Cut
Lecture 22: 4/13/11, Finish Multiway Cut, Multicut
Lecture 23: 4/15/11, Finish Multicut, Intro to Sparsest Cut
Lecture 24: 4/20/11, Sparsest Cut via Multicut, Start metric embeddings
Lecture 25: 4/22/11, Sparsest Cut via l_1 embeddings
Lecture 26: 4/27/11, Embedding finite metrics into tree metrics probabilistically
Lecture 27: 4/29/11, Semidefinite Programming and Max Cut
Lecture 28: 5/3/11, Semidefinite Programming and Closing Thoughts
Course Project Information