CS 598: Special Topics: Approximation Algorithms
Approximation algorithms for NP-hard problems are polynomial time heuristics that have provably good guarantees on the quality of their solutions. This course will provide a broad introduction to results and techniques in this area. Emphasis will be on fundamental problems and techniques that are of wide applicability.
Instructor: Chandra Chekuri- 3228
Office Hours: Tue, Thu 1-2pm and by appointment
Course mailing list: cs598cc at cs.uiuc.edu. Subscribe here.
Grading Policy: Homework every two weeks (4 to 5, 60-70% of grade) and a take home final (30-40% of grade).
Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Knowledge of some probability and linear programming would be useful. Attempt will be made 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 1: due on 9/26/06 in class – extended to 9/29/06 5pm in my office.
Homework 2: due on 10/31/06 in class.
Homework 3: due on 11/30/06 in class.
Homework 4: due on 12/12/06, 5pm in my office.
Lecture 1: 8/24/06, Intro, Steiner trees (MST heuristic, Greedy)
Lecture 2: 8/29/06, Metric-TSP, ATSP, NPO Problems, k-center
Lecture 3: 8/31/06, Set Cover, Maximum Coverage, Vertex Cover
Lecture 4: 9/05/06, Knapsack, Greedy, PTAS, FPTAS
Lecture 5: 9/07/06, Multi-processor scheduling (list scheduling, PTAS), Bin Packing (greedy)
Lecture 6: 9/12/06, APTAS for Bin Packing, Minimum makespan with precedence constraints
Lecture 7: 9/14/06, Multiway cut, k-Cut, Steiner k-cut, Isolating cut heuristic, Greedy splitting analysis
Lectures9,10: 9/21 and 9/26/06, Intro to LP and use in approximation, primal rounding for Vertex Cover and Set Cover
Lecture 11: 9/28/06, Dual fitting and primal-dual for Set cover, discussion on TUM matrices and integral polyhedra
Lecture 12: 10/3/06, Generalized assignment
Lectures13,14: 10/5 and 10/10, Max-SAT, Intro to metric methods, s-t cut, Multiway-cuts
Lecture 15: 10/12/06, Multicut, rounding via CKR method, lower bound
Lecture 16: 10/17/06, Probabilistic embedding of finite metrics into tree metrics, application to Steiner forest
Lectures17,18: 10/19 and 10/26/06, Sparsest cut, approx via multicut, l_1 embeddings.
Lecture 19: 10/31/06, Bourgain’s theorem on l_1 embeddings, finish sparsest cut, lower bound via expanders
Lecture 20: 11/2/06, Applications of sparsest cut to balanced separators etc. See Vazirani book, chapter 21.
Lectures21,22: 11/7/06, 11/9/06, Hardness of approximation, basics of reductions, examples
Lectures23,24: 11/14/06, 11/16/06, Semidefinite programming, Max-Cut, Max-2SAT(not in notes), 3-coloring
Lectures 25,26: 11/28/06,11/30/06, Primal-dual for Steiner forest and remarks Steiner network problem. See Vazirani book, chapter 22,23.
Lecture 27: 12/5/06, Routing problems. Congestion minimization via randomized rounding.
Lecture 28: 12/7/06, Class canceled.