Approximation Algorithm

ABOUT THE COURSE: Many real-world problems are NP-complete. Hence, they are unlikely to admit a polynomial-time algorithm. In this course, we will study various techniques to design efficient algorithms to compute an approximately optimal solutions.INTENDED AUDIENCE: Under-graduate and post-graduate students and faculty members.PREREQUISITES: Knowledge of algorithm design principles.INDUSTRY SUPPORT: All software companies especially Google, Microsoft, etc.

Week 1: Review of NP-CompletenessWeek 2:Approximation algorithm for the vertex cover, set cover, and traveling salesman problemWeek 3:Approximation algorithm for the Knapsack problem and the job scheduling problemsWeek 4:Basics of linear programmingWeek 5:Deterministic rounding: set cover, vertex cover problemsWeek 6:Deterministic rounding: steiner tree, facility location problemsWeek 7:Randomized rounding: max-SAT problemWeek 8:Randomized rounding: steiner tree, facility location problemsWeek 9:Primal-dual method: set coverWeek 10:Primal-dual method: steiner treeWeek 11:Semidefinite programming: max cutWeek 12:Hardness of approximation: travelling salesman problem, job scheduling