CS534APPROXIMATION ALGORITHMS3-0-0-6

Pre-requisites : 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.