Classroom and TimeC22, Mon: 14001530, Thu: 1112:30.Instructor Rajiv Raman: Office hours: Tue 16001700 Textbooks Approximation algorithms, Vijay Vazirani
 The Design of approximation algorithms, David Shmoys and David Williamson. (freely accessible webversion available here).
Lectures Date  What we covered
 Notes and Material
 4/8  What are approximation algorithms. Why do we need them, Abosolute/additive approximation, approximation ratio
  7/8  Vertex Cover
 Slides  11/8  Headbanging session 1
  14/8  No class.
  21/8  2 approximation and 4/3 approximation algorithm for minimum makespan scheduling on parallel machines (check slides above).
  25/8  Set Cover O(log n) approximation.
 Vazirani's book.
 28/8  PTAS for Knapsack
  1/9  FPTAS for Knapsack
  4/9  PTAS for scheduling on parallel machines
  6/9  PTAS for scheduling on parallel machines
  8/9  Linear Programs and LP Rounding: Vertex Cover
  8/9  Makeup lecture: LP rounding Set Cover.
  9/9  Headbanging session
  15/9  LP Rounding for MAXSAT
  17/9  Arora's PTAS for TSP
  18/9  Quiz 1
 
