Approximation Algorithms

Code: MA652 | L-T-P-C: 3-0-0-6

Course Content/ Syllabus: Vertex cover, Dominating set, Independent set, Dispersion set, Set cover, max-SAT, knapsack, bin packing, scheduling, spanners, Steiner trees, cuts, clustering, facility location, traveling salesman tour; greedy, local search, dynamic programming, linear program formulations, dual fitting, primal-dual method, rounding of linear programs, random sampling, derandomization, power of two solutions. Lower bounds on approximations and the relevant complexity classes.

Texts:

1. David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, First Edition, Cambridge University Press, 2011.
2. Vijay V. Vazirani, Approximation Algorithms, First Edition, Springer, 2004

References:

1. Sariel Har-Peled, Geometric Approximation Algorithms, American Mathematical Society, 2011
2. Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti Spaccamela and Marco Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, First Edition, Springer-Verlag, 1999.
3. Giri Narasimhan and Michiel Smid, Geometric Spanner Networks, First Edition, Cambridge University Press, 2007