UIUC
Computer Science Department

CS 598: Approximation Algorithms

Chandra Chekuri

Spring 2011

Course Summary

Approximation algorithms for NP-hard problems are polynomial time heuristics that have 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 addition 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. A rich algorithmic theory has been developed in this area and deep connections to several areas in mathematics 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 11:00am-12.15pm in Siebel Center 1105.

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

Office Hours: by appointment

Course mailing list:   cs598csc@cs.uiuc.edu. You can subscribe here.

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 (more information on topics forthcoming). 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 and exposure to probability and linear programming would be ideal. The instructor will try to make the material accessible to non-theory students who might be interested in applications. Consult the instructor if you have questions.

Study material:

  • Recommended text books
  • Another useful book: Approximation Algorithms for NP-hard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1995.
  • Lecture notes etc from Spring 2009 edition and Fall 2006 edition of this class.
  • Books on related topics: Combinatorial Optimization (Schrijver), Randomized Algorithms (Motwani-Raghavan),  The Probabilistic Method (Alon-Spencer)
  • Lecture notes from various places: CMU (Gupta-Ravi).

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 (randomized, primal-dual, dual-fitting, 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, bisection
    • 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/19/11, not to be graded.

Homework 1 given on Friday 01/28/11, due in class on Friday, 2/11/11.

Homework 2 given on Sunday 2/13/11, due in class on Friday, 2/25/11.

Homework 3 given on Wednesday 3/9/11, due in class on Wednesday, 3/30/11.

Homework 4 given on Wednesday 3/30/11, due in class on Wednesday, 4/13/11.

Homework 5 given on Friday 4/15/11, due in class on Friday, 4/29/11.

Homework 6 given on Friday 4/29/11, due 5/9/11.

Lectures:

Sample LaTeX file and algo.sty

Warning: Notes may contain errors. Please bring those to the attention of the instructor.

  • Lecture 1: 1/10/11, Introduction, Steiner trees (MST heuristic, Greedy).

    • Chapter 3 in Vazirani book

  • Lecture 2: 1/21/11, The Traveling Salesperson Problem, NP Optimization problems.

    • Chapter 3 in Vazirani book
    • Section 2.4 in Williamson-Shmoys book

  • Lecture 3: 1/26/11, Set Cover and Maximum Coverage via Greedy

    • Chapter 1 Williamson-Shmoys book
    • Chapters 1, 2 in Vazirani book

  • Lecture 4: 1/28/11, Vertex Cover and Set Cover via Linear Programming

    • Chapter 1 Williamson-Shmoys book
    • Chapters 13, 14, 15 in Vazirani book

  • Lecture 5: 2/4/11, Set Cover via Dual-Fitting

    • Chapter 1 Williamson-Shmoys book
    • Chapters 13, 14, 15 in Vazirani book

  • Lecture 6: 2/9/11, Knapsack, PTAS and FPTAS

    • Chapter 3 in Williamson-Shmoys book
    • Chapters 8 in Vazirani book

  • Lecture 7: 2/11/11, Maximum Independent Set, Packing Integer Programs

  • Lecture 8: 2/16/11, Continue previous lecture

  • Lecture 9: 2/18/11, Congestion minimization

    • Sections 5.10 and 5.11 in Williamson-Shmoys book

  • Lecture 10 (by Alina Ene): 2/23/11, Unrelated Machine Scheduling

    • Chapter 17 in Vazirani book

  • Lecture 11 (by Alina Ene): 2/25/11, Minimum-cost Generalized Assignment

    • Section 11.1 in Williamson-Shmoys book

  • Lecture 12: 3/2/11, Local Search for Max Cut and Submodular Function Maximization

  • Lecture 13: 3/4/11, Introduction to Clustering and Location Problems, k-Center

    • Chapter 5 in Vazirani book
    • Sections 2.2, 4.5, 5.8 12.1 in Williamson-Shmoys book

  • Lecture 14: 3/9/11, Local Search for k-median

    • Section 9.2 in Williamson-Shmoys book
    • Paper by Gupta and Tangwongsan

  • Lecture 15: 3/11/11, Background on LP (ellipsoid method, equivalence of separation and optimization, integer polyhedra, primal-dual method), primal-dual for Vertex Cover

    • Section 4.3, Chapter 7 in Williamson-Shmoys book
    • Chapter 12, 15 in Vazirani book

  • Lecture 16: 3/16/11, Primal-dual for Network Design (Steiner Forest)

    • Notes from 2009
    • Chapter 7 in Williamson-Shmoys book
    • Chapter 12, 15 in Vazirani book

  • Lecture 17: 3/18/11, Primal-dual for Network Design (0-1 Skew Supermodular)

    • Survey by Goemans and Williamson on primal-dual for network design.
    • Chapter 7 in Williamson-Shmoys book
    • Chapter 12, 15 in Vazirani book

  • Lecture 18: 3/30/11, Primal-dual for Network Design (0-1 Skew Supermodular)

    • Survey by Goemans and Williamson on primal-dual for network design.
    • Chapter 7 in Williamson-Shmoys book
    • Chapter 12, 15 in Vazirani book

  • Lecture 19: 4/1/11, Survivable Network Design Problem (Intro, 2k-approx, etc)

    • Survey by Goemans and Williamson on primal-dual for network design.
    • Chapter 11 in Williamson-Shmoys book
    • Chapter 23 in Vazirani book

  • Lecture 20: 4/6/11, Iterated Rounding 2-approx for Survivable Network Design Problem

    • Chapter 11 in Williamson-Shmoys book
    • Chapter 23 in Vazirani book

  • Lecture 21: 4/8/11, Intro to metric methods, Multiway Cut

    • Chapter 8 in Williamson-Shmoys book
    • Chapter 19 in Vazirani book

  • Lecture 22: 4/13/11, Finish Multiway Cut, Multicut

    • Notes from 2009 on multicut. The algorithm in the notes is different from the region growing ones given in the books below.
    • Chapter 8 in Williamson-Shmoys book
    • Chapter 20 (also Chapter 18) in Vazirani book

  • Lecture 23: 4/15/11, Finish Multicut, Intro to Sparsest Cut

    • Chapter 8 in Williamson-Shmoys book
    • Chapter 21 in Vazirani book

  • Lecture 24: 4/20/11, Sparsest Cut via Multicut, Start metric embeddings

    • Chapter 8 in Williamson-Shmoys book
    • Chapter 21 in Vazirani book

  • Lecture 25: 4/22/11, Sparsest Cut via l_1 embeddings

    • Chapter 15 in Williamson-Shmoys book
    • Chapter 21 in Vazirani book

  • Lecture 26: 4/27/11, Embedding finite metrics into tree metrics probabilistically

    • Chapter 8 in Williamson-Shmoys book

  • Lecture 27: 4/29/11, Semidefinite Programming and Max Cut

    • Chapter 6 in Williamson-Shmoys book
    • Chapter 26 in Vazirani book

  • Lecture 28: 5/3/11, Semidefinite Programming and Closing Thoughts

Course Project Information