Approximation Algorithms

Three credits · Graduate

An introduction to the study of approximation algorithms, highlighting key algorithm design techniques for approximation algorithms and the complementary study of hardness of approximation. Topics include greedy algorithms and local search, dynamic programming, deterministic and randomized rounding of linear and semidefinite programs, and the primal-dual method. Three credits.