15-854: Approximation Algorithms
- Anupam
Gupta and R. Ravi
- Time: MW 3-4:20P, Wean 5409
Course description:
The area of approximation algorithms is aimed at giving
provable guarantees on the performance of heuristics for hard
problems. The course will present general techniques (such as convex
programming-based approaches, randomness and metric methods) that
underly these algorithms. See here for more
information and admin details...
Lecture Notes
- (9/12) Introduction, TSP approximations. (RR)
- (9/14) MaxCut, Hardness of Approximations. (AG)
[ps,pdf]
- (9/19) Greedy Algorithms: Minimizing Makespan, Multiway Cut. (RR)
[ps,pdf]
- (9/21) Greedy Algorithms: Set Cover, Edge Disjoint Paths (AG)
[unedited ps,pdf]
- Avrim's notes
on the Set Cover analysis.
- (9/26) Local Search: Max-leaf Spanning Tree, Min Degree Spanning Tree. (RR)
[unedited ps,pdf]
- The
paper by
Lu and Ravi on max-leaf spanning trees.
- (9/28) Local Search: Min Degree Spanning Tree, Max-cut revisited (RR/AG)
[unedited ps,pdf]
- Notes from Kamesh
Munagala's class on min-degree spanning trees.
- (10/3) Local Search: Facility Location/K-Median. (AG)
[unedited ps,pdf]
-
Notes by Samir Khuller
(SIGACT News Algorithms column, 2001).]
- (10/5) The Local Ratio method. (RR) [see Lec9 notes.]
- (10/10) The Local Ratio method for FVS and Vertex Cover. (RR)
[unedited ps,pdf]
- The
paper of Bafna, Berman, and Fujito
giving a 2-approximation for the FVS problem.
- (10/12) Dynamic Programming: Knapsack, Scheduling. (AG)
[unedited ps,pdf]
- The Ibarra and Kim
paper giving the FPTAS for
knapsack.
- The Hochbaum and Shmoys
paper giving the PTAS for
scheduling on parallel machines (section 3).
- (10/17) Randomized Approximation Algorithms. (AG)
[unedited ps,pdf]
- The paper by Gupta, Kumar and Roughgarden on Rent-or-Buy network design.
- (10/19) Randomized Approximation: Approximating metrics by tree metrics. (AG)
[unedited ps,pdf]
- The Bartal paper giving the `O(log n \times log Delta)` and `O(log^2 n)` results.
- The Fakcharoenphol, Rao and Talwar paper giving the tight `O(log \ n)` result.
- (10/24) FOCS in Pittsburgh! No class.
- (10/26) LP: Intro to Linear Programming (RR).
[unedited ps,pdf]
- A survey by Bob Carr and Goran Konjevod on Polyhedral Combinatorics.
- (10/31) LP Rounding: Uncapacitated Facility Location. (AG)
[unedited ps,pdf]
- The original paper by Shmoys, Tardos and Aardal on filtering+clustering.
- (11/2) LP Rounding: `R||C_max` and Generalized Assignment Problems. (AG)
[unedited ps,pdf]
- The Lenstra, Shmoys and Tardos paper. Warning: 15MB file. (CMU/Pitt only.)
- The Shmoys and Tardos paper for the version with costs.
- (11/7) LP Randomized Rounding: Set Cover, Low-Congestion Routing. (RR)
- Notes on Chernoff bounds (PS, PDF) from the F04 Randomized Algos course.
Here is a more detailed treatment of Chernoff bounds by Aravind Srinivasan.
- The original randomized rounding paper by Raghavan and Thompson.
Prabhakar Raghavan's paper on derandomization using pessimistic estimators here.
- Neal Young's paper on randomized rounding without solving the LP.
- (11/9) LP Randomized Rounding: Group Steiner Tree. (RR)
[unedited ps,pdf]
- The Garg, Konjevod and Ravi paper on Group Steiner Tree.
- Notes on the proof ideas behind Janson's Inequality, from Aravind Srinivasan.
- (11/14) LP solutions as Metrics: s-t MinCut, Multiway Cut. (AG)
[unedited ps,pdf]
- (11/16) LP solutions as Metrics: MultiCut, and Region Growing. (AG)
[unedited ps,pdf]
- A survey by David Shmoys. (Sec 5.2.4 is the most relevant.)
- The Linial and Saks paper on low-diameter graph decompositions.
- The original paper of Garg, Vazirani and Yannakakis on MultiCut.
- The Leighton and Rao paper on Sparsest Cut. Lemma 3 is essentially the Region Growing theorem.
- (11/21) LP Duality and the Primal-Dual schema. (RR)
[unedited ps,pdf]
- (11/28) Primal-Dual schema: Steiner Tree. (RR)
[unedited ps,pdf]
- (11/30) Semidefinite Programming. (AG)
[unedited ps,pdf]
- (12/5) Inapproximability. (AG)
[unedited ps,pdf]
- (12/7) Lagrangean Methods. (RR)
[unedited ps,pdf]
Homeworks
- Homework 1. (9/14, due 9/21)
[ PS, PDF,
LaTeX ]
- Homework 2. (9/21, due 9/28)
[ PS, PDF,
LaTeX ]
- Solution sketches. [PS, PDF] (CMU and Pitt access only.)
- Homework 3. (9/29, due 10/05)
[ PS, PDF,
LaTeX ]
- Partial Solution sketches. [PS, PDF] (CMU and Pitt access only.)
- Homework 4. (10/11, due 10/19)
[ PS, PDF,
LaTeX ]
- Partial Solution sketches. [PS, PDF] (CMU and Pitt access only.)
- Homework 5. (11/2, due 11/9)
[ PS, PDF,
LaTeX ]
- Final. (11/30, due 12/12)
[ PS, PDF,
LaTeX ]
- Partial Solution. [PS, PDF] (CMU and Pitt access only.)
Misc Documents
- Scribe notes LaTeX template.
- Ipe: a simple yet powerful drawing editor.
- A PDF version of Mathematical Writing by Knuth, Larrabee, and Roberts. Please review pp.1-6 before you begin writing scribe notes.
Announcements from the course:
- (11/17) The time for next semester's reading course 15-859Q
is Friday 9:30A-12P, and the location is Wean 4615A.
- (12/15) Some updates on the course
- Partial solutions to HW3, HW4, and Final are online. The rest of the solutions will come soon.
- HW4's have been graded and can be picked up from Nicole Stenger (Wean 4116).
- The finals will be graded and returned soon.
- (11/30) The final exam is online. Electronic versions (PS/PDF)
will be much appreciated. (directions for submission.)
- (12/1) Final 4(a): the LP should try to maximize the
sum, not minimize it. Also the `y_i` variables are non-negative.
- (12/6) Final 4. Rounding the LP means converting the variables from
merely being in the interval `[0,1]` into variables that take one of two possible values
`{0, 1/K}` for some suitable value `K`. The integrality gap is defined similarly.
If you are confused about this idea, send mail or come by and talk to us.
- (12/9) Final 6. Dont bother about the parameter `K`: you can pick as
many sets as you want, and just need to max the number of elements picked exactly once.
- (11/28) Please fill in the
Course Evaluations
online and give us yr valuable feedback on the course.
Last updated: 10/12/2005