CS60023 Approximation and Online Algorithms
Instructor:
Sudeshna Kolay and Palash Dey
Teaching Assistants:
Aryan Sanghi
Course overview:
Many combinatorial and geometric optimization problems that arise in real-world applications are known to be NP-hard. According to computational complexity theory, designing efficient algorithms that compute exact optimal solutions for such problems is unlikely unless P = NP. Nevertheless, the need for efficient algorithms remains. A practical alternative is to relax the requirement of exact optimality and instead compute solutions that are provably close to the optimum within polynomial time. In many applications, such approximate solutions are sufficient, particularly when they can be obtained much more efficiently than exact ones. This motivates the study of approximation algorithms, which produce near-optimal solutions together with theoretical guarantees on their quality. These guarantees are expressed through the approximation ratio, which measures how close the computed solution is to the optimal one.
A related concept arises in the design of online algorithms, where decisions must be made without complete knowledge of the input. In many real-world scenarios, parts of the input become available only over time, requiring the algorithm to make irrevocable decisions based solely on the information seen so far. The performance of an online algorithm is evaluated using its competitive ratio, which compares its solution with that of an optimal offline algorithm that has access to the entire input in advance.
Classes:
Venue: CSE-302.
Timings: Monday 11-11:55 AM, Tuesday 8-9:55 AM
Extra slot: TBD.
Grading:
Attendance: 10%, Assignments: 10%, Class tests: 20%, Mid-term: 30%, Final: 30%
Announcements:
- For registering in this subject, (i) you should be a CS student, (ii) your current CGPA should be at least 8.5, and (iii) you should apply for this subject in erp by July 15.
- First class will be on July 20, 2026.
Assignments:
Lectures:
References:
- The Design of Approximation Algorithm by David P. Williamson David B. Shmoys. You can download free version here.
- Approximation Algorithms by Vijay V Vazirani. You can download free version here.
- Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv.