Approximation Algorithms
About the Course Faculty
Prof Rajiv Gandhi | Professor of Computer Science, Rutgers University–Camden & University of Pennsylvania
- Core Expertise: Algorithm Design, Combinatorial Optimization, and Probabilistic Methods.
- Industry Roots: Former Software Engineer at Qualcomm.
- Key Accolades: Recipient of the 2022 ACM-SIGACT Distinguished Service Award, a Fulbright Fellowship (Mumbai, India), and the Rutgers Provost’s Award for Teaching Excellence.
- Education: PhD in Computer Science, University of Maryland (2003).
Plaksha Modular Courses Registration Form | Winter 2026 - 2027
As part of our upcoming Winter Modular Courses (December 14-19, 2026 & January 4-9, 2027), Plaksha is offering a set of high-impact, industry-relevant modules taught by renowned global faculty. You can sign up for these courses by filling this registration form. Please note:
1. Enrollment process: This form is to register interest in attending the courses. After submission of this form, course coordinator shall review your application and take a decision on your enrolment request. If approved, you shall receive a confirmation email along with course payment link. You can sign-up for the course by paying the course fee on the link within 3 days of receiving the form.
2. Timelines: You can submit your interest by submitting this form before Nov 22, 2026.
3. Fee: The course fee is INR 20000 inclusive of GST. Accommodation fee is separate and is applicable for those who need campus accommodation.
4. Accommodation: If you need campus accommodation, please submit your request in the accommodation question given in this form. The fee for the accommodation is INR 1000 per night. You can avail food services on campus by paying per meal at the food desk.
5. Adherence to Plaksha academic guidelines and campus life rules is mandatory while you attend this course.
6. Please read through the course timelines carefully before registering your interest.
7. Courses offer:
- AI Product Management: From User Problem to Reliable Product by Dr. Anuj Kapoor
- Frontiers in Multimodal AI by Dr. Manish Gupta
- Advanced Algorithms by Prof. Rajeev Gandhi
- Cooperation and Conflict in the Global Economy by Dr. Kamal Saggi
- Program Analysis for Modern Software Tools by Prof. Rajeev Barua
- Hands-on Deep Learning: CNN and CV Applications by Prof. Hamed Hassani
- Cybersecurity and AI by Prof Rajeev Barua
- Case Studies of AI in Business by Dr. Anand Rao
- Approximation Algorithms by Prof. Rajeev Gandhi
If you have any queries regarding this course, feel free to write us at pawan.kumar@plaksha.edu.in
When you submit this form, it will not automatically collect your details like name and email address unless you provide it yourself.
Course Description
Many critical optimization problems arising in computer science, data science, network design, scheduling, and robotics are NP-hard, making it practically impossible for any algorithm to be both perfectly optimal and efficient. To cope with this intractability, we must sacrifice absolute optimality in favor of efficient polynomial-time heuristics. This course focuses on approximation algorithms—heuristics that provide rigorous, provable mathematical guarantees on the quality of their solutions, thereby quantifying their gap from optimality. We expect to cover the following techniques: greedy algorithms, local search, rounding, scaling, and dynamic programming, linear programming-based techniques -- LP-rounding and the primal-dual method.
Course Topics
| Unit | Sessions | Topics Covered |
|---|---|---|
|
Unit Combinatorial Approximation Algorithms |
Sessions 4 |
Topics Covered k-center, Traveling Salesperson Problem (TSP), Scheduling, Knapsack |
|
Unit Introduction to Linear Programming (LP) |
Sessions 1 | Topics Covered |
|
Unit LP-based Approximation Algorithms (LP-rounding + Primal-Dual) |
Sessions 4 |
Topics Covered Vertex Cover, Set Cover, Uncapacitated Facility Location, Max-SAT, Independent Set |
|
Unit Semidefinite Programming |
Sessions 1 | Topics Covered |
This course follows the academic policies established by Plaksha University’s Office of Academic Affairs, applicable uniformly across all programs.