Approximation Algorithms

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.