| 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. |