COL 754 : Approximation Algorithms

Course Coordinator

Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.

Announcements

Class Timings and Venue

Slot AC, Tuesday, Friday : 2pm-3:30pm. Venue: Block III, 342.

Homeworks

Homework 1

Lecture Topics

1. Introduction, Greedy algorithms for Vertex Cover, Set Cover. 2-approx. for Vertex Cover.
2. Analysis of greedy algorithm for weighted set cover. Introduction to Linear Programming and LP relaxation.
3. LP relaxation and rounding for vertex cover, randomized rounding for set cover, PTAS for knapsack.
4. Makespan minimization: Graham's algorithm, PTAS.
5. Max-cut: local search and greedy. 2-approx. for k-center. Local search algorithm for k-median.
6. Analysis of k-median local search algorithm. Notion of basic solution to an LP.
7. Bipartite matching using basic solution. Makespan on restricted assignment. Introduction to tail inequalities.
8. Chernoff Bounds. Congestion Minimization.
9. Proof of Chernoff Bound. Inroduction to LP Duality.
10. LP Duality, Primal Dual Algorithm for weighted Vertex Cover
11. Primal Dual Algorithm for Steiner Tree
12. Primal Dual Algorithm for Steiner forest and related problems
13. Iterative rounding, bipartite matching
14. Iterative rounding for Steiner Forest
15. Approximation by distribution over tree metrics and applications
16. Sparsest cut and embedding into L1 metric

Pre-requisites

Design and Analysis of Algorithms (COL 351 or equivalent)

Books

There is no required textbook for this course. But most of the topics covered can be found in one of these books.

1. The Design of Approximation Algorithms , by David Williamson and David Shmoys
2. Approximation Algorithms, by Vijay Vazirani

Grading

25% : Homework
30%: Mid-term Exam
40%: End-term Exam
5%: Attendance