# COL 754 : Approximation Algorithms

## Instructor

Amit Kumar

Office : Room # 417, Bharti Building

Email : amitk@cse.iitd.ac.in

Phone : (ext) 1286.

## Announcements

Homework 3 has been posted.

## Class Timings

Slot AD, Tuesday, Friday : 3:30pm-5pm.

## Homeworks

## Lecture Topics

- Lecture 1: Introduction, notion of approximation ratio

- Lecture 2: Min. makespan on identical machines, Max-coverage problem

- Lecture 3: Weighted Set cover, Vertex Cover, notion of linear programming

- Lecture 4 LP rounding for weighted vertex cover, Min. Steiner tree problem

- Lecture 5: Traveling salesman problem, Christofides' heuristic, k-center problem

- Lecture 6: Dynamic Programming, PTAS for Knapsack, Makespan for Identical Machines

- Lecture 7: PTAS for Bin Packing

- Lecture 8 : Linear Programming, Rounding for Vertrex cover, Maximum matching, Makespan on Unrelated machines via LP relaxations

- Lecture 9: Minor Exam

- Lecture 10: Notion of vertex solution. Separation oracle and Ellipsoid Algorithm. Examples.

- Lecture 11: Weighted Completion time with release dates on a single machine, Min s-t cut via LP relaxation, Idea of Randomized Rounding

- Lecture 12: Max-SAT, Min. Multi-cut problem

- Lecture 13: Unsplittable Flow Problem, Chernoff Bounds

- Lecture 14: Proof of Chernoff Bounds and applications

- Lecture 15: Tree embeddings and applications

- Lecture 16: Low distortion tree embeddings

- Lecture 17: Iterative methods, Minimum Spanning Tree by iterative relaxation

- Lecture 18: Degree bounded Minimum Spanning Tree

- Lecture 19: Steiner Network Design and Iterative Rounding

- Lecture 20: Notion of LP duality and some examples.

- Lecture 21: Primal-dual algorithms for set cover and vertex cover.

- Lecture 22: Primal-dual algorithm for facility location.

- Lecture 23: Primal-dual algorithm for Steiner forest.

- Lecture 24: Semidefinite Programming and Max-Cut SDP.

## Pre-requisites

Design and Analysis of Algorithms (COL 356 or equivalent)

## Books

There is no required textbook for this course. But most of the topics
covered can be found in one of these books.

1. The design of Approximation Algorithms, by David Williamson and David Shmoys

2. Approximation Algorithms, by Vijay Vazirani

## Grading

20% : Homework

20% : Each minor exam

40% : Major exam