CSE - IIT Kanpur

CS 635: Approximation Algorithms

Credits: 3-0-0-0 [9]

Course Objectives

Many NP-hard optimization problems admit efficient algorithms that return provably near-optimal solutions. The aim of this course is to teach students how to devise such algorithms and prove their approximation guarantees. Towards this end, the course covers the main algorithmic paradigms in the area: combinatorial methods, rounding of solutions to LP relaxations, methods utilizing LP duality, and local search. Since the same problems recur across these paradigms, the course can be taught either technique-first, applying each paradigm to several problems, or problem-first, studying each problem through several paradigms.

Course Contents

S.No.	Broad Title	Topics	No. of Lectures
1	Overview and motivation of the course	NP-hardness and the need for approximation. Introduce definitions and notions. Overview of the techniques and problems covered in the course.	1
2	Combinatorial Algorithms	(a) vertex cover and set cover (greedy, local ratio method); (b) Steiner tree (2-apx.) and TSP (2- and 1.5-apx); (c) Knapsack (2-apx, exact pseudo-polytime dynamic program, fully polynomial time approximation scheme); (d) Makespan minimization on identical/related machines (list scheduling, earliest completion time rule, polytime approximation scheme); (e) k-center (2-apx). Optional topics: Bin packing; Multiway cut and k-cut.	6
3	Linear programming based algorithms	(a) LP theory and basic results; (b) Deterministic rounding (vertex cover, set cover); (c) Randomized rounding (set cover, MAX-SAT, derandomization via conditional expectations) (d) Rounding extreme point solutions (makespan minimization on unrelated machines, generalized assignment); (e) Iterative rounding (survivable network design problem); (f) Uncapacitated facility location and k-median; Optional topics: Randomized LP rounding for multiway cut; Region growing for multicut.	7
4	Dual LP based algorithms	(a) LP duality (weak and strong duality, complementary slackness); (b) Dual fitting (set cover); (c) Primal-dual method (vertex cover and set cover, knapsack, Steiner forest, facility location, and k-median). Optional topic: multicut on trees	6
5	Local search	(a) Basics (neighbourhoods and local optima); (b) Swap-based algorithms (max-cut, makespan minimization on identical machines, k-median); (c) Add, Drop, and Swap-based algorithm (facility location)	3
6	Miscellaneous Topics	Based on availability of time and interest of students, some topics from the following list will be covered: (a) Semi-definite programming based approach for Max-Cut; (b) Hardness of approximation; (c) Iterative rounding for min-cost bounded-degree spanning tree problem; (d) Stochastic combinatorial optimization.	7

Reference books

1) Vijay V. Vazirani. Approximation Algorithms. Springer, 2001.

2) David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.

In addition, relevant research papers will be provided.

CS 635: Approximation Algorithms

Course Objectives

Course Contents

Reference books

People

Resources

Programs

Admissions

Department

Research