UIUC
Computer Science Department

CS 598: Special Topics: Approximation Algorithms

Chandra Chekuri

Fall 2006

Course Summary

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.

Administrative Information

Lectures: Tue-Thur 11-12:15 in Siebel Center 1302.

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

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.

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
    • Primal-dual
    • 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
    • Covering problems: vertex cover, set cover
    • Constraint satisfaction: max k-Sat, max-cut
    • Clustering: k-center, k-median, facility location
    • Cut problems: 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.

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, 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

Lecture 8: 9/19/06, Local search for uncapacitated facility location, local search for k-median (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 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.