Approximation Algorithms (CS6841)
Teaching Group
An Introductory Note
Coping with the rule! Most of the problems arising in Computer Science are NP-hard, and so we believe that they cannot admit a polynomial time algorithm. Despite the above setback, many problems arising in practise require us to solve these problems. Now the pragmatic approach to go forward is either to compromise on the allowed polynomial running time or to compromise on the quality of the solution (or, sometimes both).
Approximation Algorithms. The focus of this course will be on the paradigm of Approximation Algorithms, where the main focus is to stick to gold-standard of efficient computation---the polynomial time, but to compute a solution whose quality maybe slightly worse than the most optimal one. The main objective is to obtain a solution whose quality is provably quite close to the optimum. We have a rich algorithmic theory with some beautiful techniques, coupled with an interesting theory of proving best approximation ratios possible for a problem.
Our course will be centred around the following topics:
Textbooks
For ease in reference, we will call the above textbooks as WS and V., respectively in the references for lectures.
Some Practical Information
Tentative Timings: Monday 14:00-15:15, Tuesday 15:30-16:45 and Thursday 17:00-17:50.
Room: CS 34.
Evaluation (tentative) and Timelines:
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
Teaching Group
- Instructor: Akanksha Agrawal
- Teaching Assistant: C. V. Jyothishmathi
An Introductory Note
Coping with the rule! Most of the problems arising in Computer Science are NP-hard, and so we believe that they cannot admit a polynomial time algorithm. Despite the above setback, many problems arising in practise require us to solve these problems. Now the pragmatic approach to go forward is either to compromise on the allowed polynomial running time or to compromise on the quality of the solution (or, sometimes both).
Approximation Algorithms. The focus of this course will be on the paradigm of Approximation Algorithms, where the main focus is to stick to gold-standard of efficient computation---the polynomial time, but to compute a solution whose quality maybe slightly worse than the most optimal one. The main objective is to obtain a solution whose quality is provably quite close to the optimum. We have a rich algorithmic theory with some beautiful techniques, coupled with an interesting theory of proving best approximation ratios possible for a problem.
Our course will be centred around the following topics:
- Introduction, basic definitions
- Greedy approximation algorithm for Set Cover
- Linear Programming based algorithms
- Weak duality theorem, strong duality theorem
- Primal Dual method
- Dual fitting
- Randomized rounding
- Local search technique
- Scheduling algorithms
- Multicut, Multiway cuts
- Semidefinite programming
- Hardness of approximation
Textbooks
- The Design of Approximation Algorithms, Williamson and Shmoys.
- Approximation Algorithms, Vazirani.
For ease in reference, we will call the above textbooks as WS and V., respectively in the references for lectures.
Some Practical Information
Tentative Timings: Monday 14:00-15:15, Tuesday 15:30-16:45 and Thursday 17:00-17:50.
Room: CS 34.
Evaluation (tentative) and Timelines:
- (30%) Midterm Exam.
- (40%) Endsem Exam.
- (30%) Short Exams/Assignments (2-3). This component will be concretely decided based on the class strength. If the class strength permits, then we will have in-class exams with discussion time in the beginning.
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
