UIUC

CS 598: Approximation AlgorithmsChandra Chekuri


Approximation algorithms for NPhard 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 NPhard 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.
Instructor: Chandra Chekuri 3228
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 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/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).
Lecture 2: 1/21/11, The Traveling Salesperson Problem, NP Optimization problems.
Lecture 3: 1/26/11, Set Cover and Maximum Coverage via Greedy
Lecture 4: 1/28/11, Vertex Cover and Set Cover via Linear Programming
Lecture 5: 2/4/11, Set Cover via DualFitting
Lecture 6: 2/9/11, Knapsack, PTAS and FPTAS
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
Lecture 10 (by Alina Ene): 2/23/11, Unrelated Machine Scheduling
Lecture 11 (by Alina Ene): 2/25/11, Minimumcost Generalized Assignment
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, kCenter
Lecture 14: 3/9/11, Local Search for kmedian
Lecture 15: 3/11/11, Background on LP (ellipsoid method, equivalence of separation and optimization, integer polyhedra, primaldual method), primaldual for Vertex Cover
Lecture 16: 3/16/11, Primaldual for Network Design (Steiner Forest)
Lecture 17: 3/18/11, Primaldual for Network Design (01 Skew Supermodular)
Lecture 18: 3/30/11, Primaldual for Network Design (01 Skew Supermodular)
Lecture 19: 4/1/11, Survivable Network Design Problem (Intro, 2kapprox, etc)
Lecture 20: 4/6/11, Iterated Rounding 2approx for Survivable Network Design Problem
Lecture 21: 4/8/11, Intro to metric methods, Multiway Cut
Lecture 22: 4/13/11, Finish Multiway Cut, Multicut
Lecture 23: 4/15/11, Finish Multicut, Intro to Sparsest Cut
Lecture 24: 4/20/11, Sparsest Cut via Multicut, Start metric embeddings
Lecture 25: 4/22/11, Sparsest Cut via l_1 embeddings
Lecture 26: 4/27/11, Embedding finite metrics into tree metrics probabilistically
Lecture 27: 4/29/11, Semidefinite Programming and Max Cut
Lecture 28: 5/3/11, Semidefinite Programming and Closing Thoughts
Course Project Information