Course Objective

This is an advanced elective which assumes familiarity with the basic techniques for algorithm analysis and design. This first two parts of this course will familiarise students to methods of dealing with hard problems using various approximation algorithm design techniques ranging from combinatorial techniques to more sophisticated LP based and probabilistic methods. It will also introduce students to different types of approximation algorithms like constant factor approximations, PTAS and FPTAS. The last part of the course gives an exposure to widely used reduction techniques for proving inapproximability of problems. The concepts and techniques will be introduced using a variety of sample illustrative problems.

Part 1 : Combinatorial Techniques: Basics - Review of NP Hardness and reductions, approximation factor, technique of lower bounding optimum - simple approximation for vertex cover, greedy algorithm for set cover. Minimum spanning tree heuristic - metric Steiner tree and metric TSP. Layering technique - feedback vertex set. Strong NP-Hardness and pseudo-polynomial-time algorithms - knapsack. Dynamic programming - PTAS for Euclidean TSP, FPTAS for the knapsack, asymptotic PTAS for bin packing. Local search - max-cut, facility location problem. (15 lectures)

Part 2 : Algorithms using LP based and probabilistic techniques: Simple rounding - max-SAT with small clauses, set cover, bin-packing. Random sampling and derandomization - max SAT, max-cut. Randomized rounding - set cover, multiway cut. Dual fitting - set cover. Primal-dual method - set Cover, steiner forest. (15 lectures)

Part 3 : Hardness of Approximation: Techniques in proving the hardness of approximation: reductions from NP-complete problems, hardness of approximation of TSP, Reductions that preserve approximation, Reductions from probabilistically checkable proofs, Reductions based on unique games conjecture - tight hardness of max-cut and vertex cover. (10 lecture)

Learning Outcomes:

  1. To be able to identify the design technique used in a given approximation algorithm.
  2. To be able to design and analyze approximation algorithms using various combinatorial approximation techniques taught in the course.
  3. To be able to apply more sophisticated techniques like randomization and LP based optimization to computationally hard, yet simple optimization problems.
  4. To be able to apply reduction techniques of proving hardness of approximation of simple combinatorial problems.

Textbook

  1. Approximation Algorithms by Vijay V. Vazirani. Springer-Verlag Berlin Heidelberg, 2003. ISBN: 978-3-642-08469-0.

Reference

  1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys. Cambridge University Press, 2011. ISBN: 978-0521195270.

  2. Approximation Algorithms for NP-Hard Problems by Dorit S. Hochbaum (Ed). PWS Publishing Company, 1997. ISBN: 978-0534949686.

Past Offerings

  • Offered in Jul-Dec, 2020 by Jasine
  • Offered in Jan-May, 2019 by Jasine

Course Metadata

Item Details
Course Title Approximation Algorithms
Course Code CS5004
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Jasine Babu
Approved on Senate 6 of IIT Palakkad
Course prerequisites A first course in the design and analysis of algorithms
Course status New