UIUC
Computer Science Department

CS 598: Special Topics: Approximation Algorithms

Chandra Chekuri

Spring 2009


Course Summary

Approximation algorithms for NP-hard 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 NP-hard 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.


Administrative Information

Lectures: Wed, Fri 12:30-1.45pm in Siebel Center 1302.

Instructor:  Chandra Chekuri- 3228 Siebel Center, 265-0705, chekuri at cs dot uiuc dot edu

Office Hours: Friday 2-3pm or by appointment

Course TA: Nitish Korula (mail). Office hours and location: Tuesdays 11:15-12: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 non-theory students who might be interested in applications. Consult the instructor if you have questions.


Study material:

Tentative Topic List:

  • Intro and Methodology: P vs NP, NP Optimization problems, Approximation Ratio, Additive vs Multiplicative, Pros and Cons.
  • Techniques:
    • Greedy and combinatorial methods
    • Local search
    • Dynamic programming and approximation schemes
    • Linear programming rounding methods
    • Primal-dual
    • Iterated Rounding
    • Semi-definite program based rounding
    • Metric methods
  • Problems:
    • Tour problems: Metric-TSP, Asymmetric TSP, TSP Path, Orienteering
    • Number Problems: knapsack, bin packing
    • Scheduling: multiprocessor scheduling, precedence constraints, generalized assignment
    • Connectivity and network design: Steiner trees, Steiner forests, Buy at bulk network design, Survivable Network Design
    • Covering problems: vertex cover, set cover
    • Constraint satisfaction: max k-Sat
    • Clustering: k-center, k-median, facility location
    • Cut problems: max cut, multiway cut, k-cut, multicut, sparsest cut
    • Routing problems: congestion minimization, maximum disjoint paths, unsplittable flow
  • Hardness of approximation: simple proofs, approximation preserving reductions, some known results

 

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.

Course Project Information

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, k-Cut, Gomory-Hu trees.

Lecture 8: 2/13/09, Clustering and Local Search: k-Center, k-Median, Max-Cut. (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, Primal-Dual for Vertex Cover, Intro to Network Design, Steiner Forest: LP and Ellipsoid method. No notes.

Lecture 12: 2/27/09, Primal-Dual 2-approximation for Steiner Forest.

Lecture 13: 3/04/09, "Abstract" Network Design: Proper, Downward Monotone, and Skew-supermodular functions. Steiner Network Problem. (Preliminary Draft)

Lecture 14: 3/06/09, A 2-approximation for the Generalized Steiner Network problem. (Draft Notes)

Lecture 15: 3/11/09, Completing the Generalized Steiner Network problem; Comments on Element- and Vertex-Connectivity. Introduction to Metrics. (See notes for Lecture 14.)

Lecture 16: 3/13/09, 2-approximation for Multiway-Cut via LP. Introduce CKR geometric relaxation.

Lecture 17: 3/18/09, Multiway-Cut: A 3/2-approximation via the CKR Geometric Relaxation.

Lecture 18: 3/20/09, Multi-Cut: 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, L1 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 Semi-definite Programs. MAX-CUT and CSPs.

Lecture 26: 4/24/09, SDPs for Max-2-Sat. Statement of results for CSPs and Sparsest Cut.

Lecture 27: 4/29/09, Hardness of Approximation: basic reductions (k-Center, Max EDP in dir graphs), definition of gap reductions.

Lecture 28: 05/01/09, Hardness of Approximation contd. PCP theorem and MAX-3-SAT hardness and reductions to Independent Set, Vertex Cover, Steiner tree. Gap Amplification for Clique.