COL 754 : Approximation Algorithms
Instructor
Amit Kumar
Office : Room # 417, Bharti Building
Email : amitk@cse.iitd.ac.in
Phone : (ext) 1286.
Announcements
Homework 3 has been posted.
Class Timings
Slot AD, Tuesday, Friday : 3:30pm-5pm.
Homeworks
Lecture Topics
- Lecture 1: Introduction, notion of approximation ratio
- Lecture 2: Min. makespan on identical machines, Max-coverage problem
- Lecture 3: Weighted Set cover, Vertex Cover, notion of linear programming
- Lecture 4 LP rounding for weighted vertex cover, Min. Steiner tree problem
- Lecture 5: Traveling salesman problem, Christofides' heuristic, k-center problem
- Lecture 6: Dynamic Programming, PTAS for Knapsack, Makespan for Identical Machines
- Lecture 7: PTAS for Bin Packing
- Lecture 8 : Linear Programming, Rounding for Vertrex cover, Maximum matching, Makespan on Unrelated machines via LP relaxations
- Lecture 9: Minor Exam
- Lecture 10: Notion of vertex solution. Separation oracle and Ellipsoid Algorithm. Examples.
- Lecture 11: Weighted Completion time with release dates on a single machine, Min s-t cut via LP relaxation, Idea of Randomized Rounding
- Lecture 12: Max-SAT, Min. Multi-cut problem
- Lecture 13: Unsplittable Flow Problem, Chernoff Bounds
- Lecture 14: Proof of Chernoff Bounds and applications
- Lecture 15: Tree embeddings and applications
- Lecture 16: Low distortion tree embeddings
- Lecture 17: Iterative methods, Minimum Spanning Tree by iterative relaxation
- Lecture 18: Degree bounded Minimum Spanning Tree
- Lecture 19: Steiner Network Design and Iterative Rounding
- Lecture 20: Notion of LP duality and some examples.
- Lecture 21: Primal-dual algorithms for set cover and vertex cover.
- Lecture 22: Primal-dual algorithm for facility location.
- Lecture 23: Primal-dual algorithm for Steiner forest.
- Lecture 24: Semidefinite Programming and Max-Cut SDP.
Pre-requisites
Design and Analysis of Algorithms (COL 356 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
20% : Homework
20% : Each minor exam
40% : Major exam