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.

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).