Welcome to Department of Mathematics

Mail Us

Call Us

Approximation Algorithms

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

Prerequisites: MA 512 Data Structures & Algorithms or MA 252 Design and Analysis of Algorithms or equivalent

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.


  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


  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