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).