COMP760: Approximation Algorithms (Winter 2010)

Mohit Singh
Office: Room 324, McConnell Building
Contact: mohit (at) cs (dot) mcgill (dot) ca
Lecture: TR 8:35-9:55AM 10:00AM-11:30AM, McConnell 320
Office Hours: Fri 2:30-4:00PM, McConnell 324

Course description:

The area of approximation algorithms deals with finding provable guarantees on the performance of heuristic solutions to hard combinatorial optimization problems. The course will present a variety of techniques that have been developed in the area of approximation algorithms ranging from dynamic programming, greedy methods, mathematical programming, randomization and metric methods. See here for more information...

Textbook

Other References

Lectures

  1. (05/01) Introduction, Set Cover
  2. (07/01) (Greedy) Vertex Cover, k-cover
  3. (12/01) (Greedy) k-center, scheduling on parallel machines
  4. (14/01) (Local Search) Scheduling on parallel machines, minimum degree spanning tree
  5. (19/01) (Local Search) k-median
  6. (21/01) (Dynamic Programming) Knapsack problem
  7. (26/01) (Dynamic Programming) Scheduling on parallel machines
  8. (28/01) (LP) Linear Programming Introduction, Set Cover, Vertex Cover
  9. (2/02) (Randomized Rounding) MAX-SAT, Derandomization.
  10. (2/04) (Randomized Rounding) Congestion Minimization in Integral Multicommodity flow, Chernoff-Hoeffding Bounds
  11. (2/09) (LP Rounding) Weighted Sum of Completion Times, Separation and Optimization
  12. (2/11) (Metric Methods) Multiway Cut
  13. (2/16) (Metric Methods) Multicut
  14. (2/18) (Metric Methods) Probabilistic embeddings in Tree Metrics
  15. (3/2) (Primal Dual Method) Feedback Vertex Set
  16. (3/4) (Primal Dual Method) Generalized Steiner Tree
  17. (3/9) (Iterative Methods) Generalized Assignment
  18. (3/11) (Iterative Methods) Bounded Degree Spanning Trees
  19. (3/16) (Iterative Methods) Survivable Network Design
  20. (3/18) (Semi-Definite Programming) Max-Cut
  21. (3/23) (Semi-Definite Programming) Coloring
  22. (3/25) (Hardness of Approximation) Reductions for TSP, Edge-Disjoint Paths
  23. (4/6) (Hardness of Approximation, PCP) MAX-3-SAT, Vertex Cover
  24. (4/8) (Unique Games) Approximation for Unique Games

Homeworks

  1. Homework 1 (pdf) Due Jan 28
    • Solution Sketches. (pdf)
  2. Homework 2 (pdf) Due Feb 16
  3. Homework 3 (pdf) Due March 4
  4. Homework 4 (pdf) Due March 18
  5. Homework 5 (pdf) Due April 6
  6. Final Exam (pdf) Due April 20