Course number ? Monsoon 2014.

Classroom and Time

C-22, Mon: 1400-1530, Thu: 11-12:30.


Rajiv Raman: Office hours: Tue 1600-1700


  • Approximation algorithms, Vijay Vazirani
  • The Design of approximation algorithms, David Shmoys and David Williamson. (freely accessible web-version available here).


 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
 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 Make-up lecture: LP rounding Set Cover.
 9/9   Headbanging session
 15/9 LP Rounding for MAX-SAT
 17/9 Arora's PTAS for TSP
 18/9    Quiz 1

Subpages (1): Description