Pre-requisites : CS204 Algorithms or equivalent
Approximation algorithms: Set cover, max-SAT, knapsack, bin packing, scheduling, spanners, Steiner trees, cuts, clustering, facility location, traveling salesman tour, network design, metric embeddings. Design techniques: greedy, local search, dynamic programming, linear program formulations, dual fitting, primal-dual method, rounding of linear/semidefinite programs, random sampling, derandomization, power of two solutions. Lower bounds on approximations and the relevant complexity classes.
1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, 1/e, Cambridge University Press, 2011.
2. Approximation Algorithms by Vijay V. Vazirani, 1/e, Springer, 2004.
1. Approximation Algorithms for NP-hard Problems edited by Dorit S. Hochbaum, 1/e, Course Technology, 1996.
2. Geometric Approximation Algorithms by Sariel Har-Peled, 1/e, American Mathematical Society, 2011.
3. Design and Analysis of Approximation Algorithms by Ding-Zhu Du, Ker-I Ko, 1/e, Springer, 2012.