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. Such algorithms are one robust way to cope with
intractable problems that arise in many areas of Computer Science and
beyond. In additon to being directly useful in applications,
approximation algorithms allow us to explore the structure of NPhard
problems and distinguish between different levels of difficulty that
these problems exhibit in theory and practice. Over the last 30 years
a rich algorithmic theory has been developed in this area and deep
connections to many areas in mathematics and natural sciences 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: Friday 23pm or by appointment
Course TA: Nitish Korula (mail). Office hours and location: Tuesdays 11:1512:15, 3240 Siebel Center.
Course news group: cs.class.cs598cc
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. 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 of some probability and linear programming would be ideal. 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.
Homework:
Homework 0 given on 01/23/09, not to be graded.
Homework 1 given on 02/03/09, due on 02/18/09 in class.
Homework 2 given on 02/18/09, due on 03/04/09 in class.
Homework 3 given on 03/06/09, due on 03/20/09 in class.
Homework 4 given on 03/20/09, due on 04/08/09 in class.
Homework 5 given on 04/08/09, due on 04/22/09 in class.
Homework 6 given on 04/22/09, due on 05/06/09 in class.
Lectures:
Sample LaTeX file and algo.sty
Warning! Notes marked as drafts are likely to contain errors; use at your own risk. Corrected versions will be forthcoming.
Lecture 1: 1/21/09, Introduction, Steiner trees (MST heuristic, Greedy). (LaTeX)
Lecture 2: 1/23/09, The Traveling Salesperson Problem, NP Optimization problems.
Lecture 3: 1/28/09, The Set Cover Problem, NP Optimization problems.
Lecture 4: 1/30/09, Knapsack: The Greedy Algorithm, PTAS and FPTAS.
Lecture 5: 2/4/09, Multiprocessor scheduling: list scheduling and PTAS. Bin Packing: greedy algorithms.
Lecture 6: 2/6/09, More Bin Packing: Asymptotic PTAS and FPTAS, etc. Multiprocessor scheduling with precedence constraints.
Lecture 7: 2/11/09, Cut Problems: Multiway cut, kCut, GomoryHu trees.
Lecture 8: 2/13/09, Clustering and Local Search: kCenter, kMedian, MaxCut. (Notes link to the paper of Gupta and Tangwongsan.)
Lecture 9: 2/18/09, Linear Programming: Overview, Vertex Cover, Set Cover.
Lecture 10: 2/20/09, Set Cover: Randomized Rounding and Dual Fitting. Totally Unimodular Matrices.
Lecture 11: 2/25/09, PrimalDual for Vertex Cover, Intro to Network Design, Steiner Forest: LP and Ellipsoid method. No notes.
Lecture 12: 2/27/09, PrimalDual 2approximation for Steiner Forest.
Lecture 13: 3/04/09, "Abstract" Network Design: Proper, Downward Monotone, and Skewsupermodular functions. Steiner Network Problem. (Preliminary Draft)
Lecture 14: 3/06/09, A 2approximation for the Generalized Steiner Network problem. (Draft Notes)
Lecture 15: 3/11/09, Completing the Generalized Steiner Network problem; Comments on Element and VertexConnectivity. Introduction to Metrics. (See notes for Lecture 14.)
Lecture 16: 3/13/09, 2approximation for MultiwayCut via LP. Introduce CKR geometric relaxation.
Lecture 17: 3/18/09, MultiwayCut: A 3/2approximation via the CKR Geometric Relaxation.
Lecture 18: 3/20/09, MultiCut: An O(log k)approximation and a lower bound on integrality gap via expanders.
Lecture 19: 4/01/09, Sparsest Cut  motivation, LP and connections. Rounding via Multicut. (Preliminary Draft).
Lecture 20: 4/03/09, Sparsest Cut and Introduction to Metric Embeddings. (Preliminary Draft).
Lecture 21: 4/08/09, L_{1} metrics, and completing Sparsest Cut. Introduction to Tree Metrics. (Preliminary Draft).
Lecture 22: 4/10/09, Routing problems. Congestion Minimization and Unsplittable Flow (lecture by Nitish Korula).
Lecture 23: 4/15/09, Padded Decomposition and Embedding into Tree metrics. (Preliminary Draft).
Lecture 24: 4/17/09, Applications of Tree Embeddings. Introduction to Convex Programming and SDPs. (Preliminary Draft).
Lecture 25: 4/22/09, Quadratic and Semidefinite Programs. MAXCUT and CSPs.
Lecture 26: 4/24/09, SDPs for Max2Sat. Statement of results for CSPs and Sparsest Cut.
Lecture 27: 4/29/09, Hardness of Approximation: basic reductions (kCenter, Max EDP in dir graphs), definition of gap reductions.
Lecture 28: 05/01/09, Hardness of Approximation contd. PCP theorem and MAX3SAT hardness and reductions to Independent Set, Vertex Cover, Steiner tree. Gap Amplification for Clique.