Approximation Algorithms

Course description

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.

Instructor

Syamantak Das

B-512, New Academic Block

Email : syamantak@...

Office hours : Only by appointment (drop an email)

Evaluation

Homework Assignments : 50%

Mid-sem : 25%

Paper presentation : 25 %

Exams

TBA

Material

[WS] Design of Approximation Algorithms, D. Shmoys and D. Williamson

[VV] Approximation Algorithms, Vijay V. Vazirani

Disclaimer : The Board Work section contains pdfs of my scribbles during the lecture and are highly unedited, contains errors typos etc.

Latex template for solutions