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 NPHardness and pseudopolynomialtime algorithms  knapsack. Dynamic programming  PTAS for Euclidean TSP, FPTAS for the knapsack, asymptotic PTAS for bin packing. Local search  maxcut, facility location problem. (15 lectures)
Part 2 : Algorithms using LP based and probabilistic techniques: Simple rounding  maxSAT with small clauses, set cover, binpacking. Random sampling and derandomization  max SAT, maxcut. Randomized rounding  set cover, multiway cut. Dual fitting  set cover. Primaldual method  set Cover, steiner forest. (15 lectures)
Part 3 : Hardness of Approximation: Techniques in proving the hardness of approximation: reductions from NPcomplete problems, hardness of approximation of TSP, Reductions that preserve approximation, Reductions from probabilistically checkable proofs, Reductions based on unique games conjecture  tight hardness of maxcut and vertex cover. (10 lecture)
Learning Outcomes:
 To be able to identify the design technique used in a given approximation algorithm.
 To be able to design and analyze approximation algorithms using various combinatorial approximation techniques taught in the course.
 To be able to apply more sophisticated techniques like randomization and LP based optimization to computationally hard, yet simple optimization problems.
 To be able to apply reduction techniques of proving hardness of approximation of simple combinatorial problems.
Textbook
 Approximation Algorithms by Vijay V. Vazirani. SpringerVerlag Berlin Heidelberg, 2003. ISBN: 9783642084690.
Reference

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

Approximation Algorithms for NPHard Problems by Dorit S. Hochbaum (Ed). PWS Publishing Company, 1997. ISBN: 9780534949686.
Past Offerings
 Offered in JulDec, 2020 by Jasine
 Offered in JanMay, 2019 by Jasine