15-854(B): Advanced Approximation Algorithms, Spring 2008

Lecturers: Anupam Gupta and Ryan O'Donnell

Time: TuTh 1:30-2:50, Wean 5409

Course Blog: http://approximability.blogspot.com/

Handouts:

      Course information
      How to scribe
      Definitions of some NP optimization problems we'll study

Homework:

      Homework 1 (due Tuesday, January 29, beginning of class)
      Homework 2 (due Tuesday, Feb 12, beginning of class)
      Homework 3 (due Thursday, Feb 28, beginning of class)
      Homework 4 (due Thursday, Mar 20, beginning of class)
      Homework 5 (due Tuesday, ~~April 1~~ April 3, beginning of class)
      Homework 6 (due Thursday, May 1, beginning of class)

Lecture notes (unedited):

      Scribe style file: scribe.sty
      Lecture 1: Definitions; greedy algorithm for Set-Cover and Max-Coverage (lecturer: Ryan; scribe: Dafna Shahaf)
      Lecture 2: LP rounding algorithms and gaps for Set-Cover and Max-Coverage (lecturer: Ryan; scribe: Ali Kemal Sinop)
      Lecture 3: 1 vs. 3/4 + eps hardness for Max-Coverage (lecturer: Ryan; scribe: Ravishankar Krishnaswamy)
      Lecture 4: Facility Location; constant factor LP rounding (lecturer: Anupam, scribe: S. Harsha Vardhan)
      Lecture 5: Facility Location; primal-dual algorithms (lecturer: Anupam, scribe: Varun Gupta)
      Lecture 6: Facility Location; greedy and local-search algorithms (lecturer: Anupam, scribe: Viswanath Nagarajan)
      Lecture 7: K-center: symmetric and asymmetric variants (lecturer: Anupam, scribe: Jeremiah Blocki)
      Lecture 8: Hardness of Min-Ek-Hypergraph-Independent-Set (lecturer: Ryan, scribe: Aaron Roth)
      Lecture 9: Finishing hardness for Hypergraph-Independent-Set and Asymmetric-k-Center (lecturers: Ryan and Anupam, scribe: Eric Blais)
      Lecture 10: Group Steiner Tree (lecturer: Anupam, scribe: Amitabh Basu)
      Lecture 11: Group Steiner Tree Gaps and Hardness (lecturer: Anupam, scribe: Kanat Tangwongsan)
      Lecture 12: Steiner Tree Problems (lecturer: Anupam, scribe: Mike Dinitz)
      Lecture 13: Priority Steiner Tree integrality gap and hardness (lecturer: Anupam, scribe: Evan Danaher)
      Lecture 14: Semidefinite programming and Max-Cut (lecturer: Ryan, scribe: Ali Kemal Sinop)
      Lecture 15: Coloring 3-colorable graphs (lecturer: Ryan, scribe: Dafna Shahaf)
      Lecture 16: Gaps for Max-Cut (lecturer: Ryan, scribe: Ravishankar Krishnaswamy)
      Lecture 17: Introduction to Fourier analysis (lecturer: Ryan, scribe: Viswanath Nagarajan)
      Lecture 18: Multicut (lecturer: Anupam, scribe: Kanat Tangwongsan)
      Lecture 19: Sparsest Cut (lecturer: Anupam, scribe: Amitabh Basu)
      Lecture 20: Embeddings into Trees and L1 Embeddings (lecturer: Anupam, scribe: Aaron Roth)
      Lecture 21: Intro to CSP hardness; why Dictator tests? (lecturer: Ryan, scribe: Michael Dinitz)
      Lecture 22: Beginning 3Lin hardness: the basic test (lecturer: Ryan, scribe: Evan Danaher)
      Lecture 23: Finishing 3Lin hardness (lecturer: Ryan, scribe: Jonah Sherman)
      Lecture 24: UG-Hardness of Max-Cut and Multicut (lecturer: Ryan, scribe: S. Harsha Vardhan)
      Lecture 25: NP-Hardness of Max-kCSP and Independent-Set/Clique (lecturer: Ryan, scribe: Eric Blais)
      Lecture 26: NP-Hardness of Max-2Lin (lecturer: Ryan, scribe: Jeremiah Blocki)
      Lecture 27: Sparsest Cut revisited: the SDP (lecturer: Anupam, scribe: Varun Gupta)
      Lecture 28: More on Sparsest Cut (lecturer: Anupam, scribe: )
      Lecture 29: Bin Packing (lecturer: Anupam, scribe: )

Course description:

Since many important problems are known to be NP complete, recent research in algorithms has sought to develop heuristics for these problems that have provable guarantees on their performance. In particular, given an instance of an NP-hard optimization problem, a `C`-approximation algorithm outputs a solution that has cost at most `C` times the cost of the optimal solution. This has been complemented by research on the "hardness of approximation" for such problems: this involves showing values of D such that obtaining a D-approximation is provably hard (under complexity-theoretic assumptions).

In this course, we will study some algorithms for which we know matching (or nearly-matching) bounds on the approximability, stressing techniques and tools required to prove both the upper and lower bounds.

Prerequisites:

Students should have taken a graduate algorithms course (15-851 or equivalent) and a graduate complexity course (15-855 or equivalent). If you do not have the pre-reqs (and do not have a strong Theory/Algorithms background), please speak to the us before you decide to take the course.

If you have taken the previous approximations algorithms course from Fall 2005, you can (and perhaps should) take this course, since we will cover more advanced topics.

Text:

There is no text for the course, so papers and notes will be distributed as necessary. The book Approximation Algorithms by V.V.Vazirani touches on many of the upper bound techniques.

This material is based upon work supported by the National Science Foundation under Grant No. CCF-0747250. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).