15-854: Approximation Algorithms

Anupam Gupta and R. Ravi

Time: MW 3-4:20P, Wean 5409

Lecture Notes

1. (9/12) Introduction, TSP approximations. (RR)
2. (9/14) MaxCut, Hardness of Approximations. (AG) [ps,pdf]
3. (9/19) Greedy Algorithms: Minimizing Makespan, Multiway Cut. (RR) [ps,pdf]
4. (9/21) Greedy Algorithms: Set Cover, Edge Disjoint Paths (AG) [unedited ps,pdf]
   • Avrim's notes on the Set Cover analysis.
5. (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.
6. (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.
7. (10/3) Local Search: Facility Location/K-Median. (AG) [unedited ps,pdf]
   • Notes by Samir Khuller (SIGACT News Algorithms column, 2001).]
8. (10/5) The Local Ratio method. (RR) [see Lec9 notes.]
9. (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. (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).
11. (10/17) Randomized Approximation Algorithms. (AG) [unedited ps,pdf]
    • The paper by Gupta, Kumar and Roughgarden on Rent-or-Buy network design.
12. (10/19) Randomized Approximation: Approximating metrics by tree metrics. (AG) [unedited ps,pdf]
    • The Bartal paper giving the ${\displaystyle O(logn\times log\Delta )}$ and ${\displaystyle O\left({log}^{2}n\right)}$ results.
    • The Fakcharoenphol, Rao and Talwar paper giving the tight ${\displaystyle O(log n)}$ result.
13. (10/24) FOCS in Pittsburgh! No class.
14. (10/26) LP: Intro to Linear Programming (RR). [unedited ps,pdf]
    • A survey by Bob Carr and Goran Konjevod on Polyhedral Combinatorics.
15. (10/31) LP Rounding: Uncapacitated Facility Location. (AG) [unedited ps,pdf]
    • The original paper by Shmoys, Tardos and Aardal on filtering+clustering.
16. (11/2) LP Rounding: ${\displaystyle R\left|\right|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.
17. (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.
18. (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.
19. (11/14) LP solutions as Metrics: s-t MinCut, Multiway Cut. (AG) [unedited ps,pdf]
20. (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.
21. (11/21) LP Duality and the Primal-Dual schema. (RR) [unedited ps,pdf]
22. (11/28) Primal-Dual schema: Steiner Tree. (RR) [unedited ps,pdf]
    • The AKR (Agarwal, Klein and Ravi) paper, and the GW (Goemans and Williamson) paper on PD for Steiner problems.
    • Surveys by Goemans and Williamson and Cheriyan and Ravi on PD Network Design.
23. (11/30) Semidefinite Programming. (AG) [unedited ps,pdf]
    • The Max-Cut paper of Goemans and Williamson.
    • Surveys by Feige, by Goemans, and by Laurent and Rendl on SDPs in approximation algorithms.
    • A survey by Lovasz on Semidefinite Optimization.
24. (12/5) Inapproximability. (AG) [unedited ps,pdf]
25. (12/7) Lagrangean Methods. (RR) [unedited ps,pdf]

Homeworks

1. Homework 1. (9/14, due 9/21) [ PS, PDF, LaTeX ]
2. Homework 2. (9/21, due 9/28) [ PS, PDF, LaTeX ]
   • Solution sketches. [PS, PDF] (CMU and Pitt access only.)
3. Homework 3. (9/29, due 10/05) [ PS, PDF, LaTeX ]
   • Partial Solution sketches. [PS, PDF] (CMU and Pitt access only.)
4. Homework 4. (10/11, due 10/19) [ PS, PDF, LaTeX ]
   • Partial Solution sketches. [PS, PDF] (CMU and Pitt access only.)
5. Homework 5. (11/2, due 11/9) [ PS, PDF, LaTeX ]


6. Final. (11/30, due 12/12) [ PS, PDF, LaTeX ]
   • Partial Solution. [PS, PDF] (CMU and Pitt access only.)

Misc Documents

1. Scribe notes LaTeX template.
2. Ipe: a simple yet powerful drawing editor.
3. 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:

1. (11/17) The time for next semester's reading course 15-859Q is Friday 9:30A-12P, and the location is Wean 4615A.


2. (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.


3. (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 ${\displaystyle y_i}$ variables are non-negative.
   • (12/6) Final 4. Rounding the LP means converting the variables from merely being in the interval ${\displaystyle [0,1]}$ into variables that take one of two possible values ${\displaystyle \{0,\frac{1}{K}\}}$ for some suitable value ${\displaystyle 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 ${\displaystyle K}$: you can pick as many sets as you want, and just need to max the number of elements picked exactly once.


4. (11/28) Please fill in the Course Evaluations online and give us yr valuable feedback on the course.

Last updated: 10/12/2005