Course number ? Monsoon 2014.

Classroom and Time

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

Instructor

Rajiv Raman: Office hours: Tue 1600-1700

Textbooks

  • Approximation algorithms, Vijay Vazirani
  • The Design of approximation algorithms, David Shmoys and David Williamson. (freely accessible web-version 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 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