UIUC

CS 598: Special Topics: Approximation AlgorithmsChandra Chekuri


Approximation algorithms for NPhard 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 12pm and by appointment
Course mailing list: cs598cc at cs.uiuc.edu. Subscribe here.
Grading Policy: Homework every two weeks (4 to 5, 6070% of grade) and a take home final (3040% 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 nontheory 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.
Homeworks:
Homework 0: given on 8/24/06, not to be graded
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.
Lectures:
Lecture 1: 8/24/06, Intro, Steiner trees (MST heuristic, Greedy)
Lecture 2: 8/29/06, MetricTSP, ATSP, NPO Problems, kcenter
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, Multiprocessor 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, kCut, Steiner kcut, Isolating cut heuristic, Greedy splitting analysis
Lecture 8: 9/19/06, Local search for uncapacitated facility location, local search for kmedian (not covered in class)
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 primaldual for Set cover, discussion on TUM matrices and integral polyhedra
Lecture 12: 10/3/06, Generalized assignment
Lectures13,14: 10/5 and 10/10, MaxSAT, Intro to metric methods, st cut, Multiwaycuts
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, MaxCut, Max2SAT(not in notes), 3coloring
Lectures 25,26: 11/28/06,11/30/06, Primaldual 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.