CDS 409: Approximation Algorithms
Fall 2026
- Instructor: Satyabrata Jana ( satyabrataj [at] iiserbpr [dot] ac [dot] in )
- Timings: Monday (9 – 10 AM), Thursday (11 – 12 PM), Friday (9 – 10 AM)
- Venue: Room No. 2006, 2nd Floor, Block 6
- Grading: End-Sem Exam (40%), Mid-Sem Exam (30%), Assignments (20%), Attendance (10%)
Objectives
This course introduces algorithmic techniques for addressing computationally hard optimization problems for which finding exact solutions efficiently may not be feasible. Students will learn to design and analyse approximation algorithms with provable performance guarantees. Through classical problems and practical applications, they will develop an understanding of the trade-offs between solution quality and computational efficiency. The course also aims to strengthen problem-solving abilities, mathematical reasoning, and rigorous algorithmic analysis skills.
Prerequisites
Students are expected to be familiar with basic data structures and algorithms, graph algorithms, and asymptotic analysis. A working knowledge of discrete mathematics, probability, linear algebra, and standard proof techniques is desirable. Familiarity with computational complexity, particularly NP-completeness, will be helpful.
References
- The Design of Approximation Algorithms – David P. Williamson, David B. Shmoys
- Approximation Algorithms – Vijay V. Vazirani
- Approximation Algorithms for NP-hard Problems – Dorit S. Hochbaum
- Design and Analysis of Approximation Algorithms – Ding-Zhu Du, Ker-I Ko, Xiaodong Hu
- Geometric Approximation Algorithms – Sariel Har-Peled
Lectures
- Lecture 1 (03.08.2026): Introduction to the course.