Course Code: CS534
Course Name: Approximation Algorithms
Prerequisites: CS204 Algorithms or equivalent
Syllabus: 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.
Texts: 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.
References: 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.