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.
B-512, New Academic Block
Email : syamantak@...
Office hours : Only by appointment (drop an email)
Homework Assignments : 50%
Mid-sem : 25%
Paper presentation : 25 %
[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.
The problems sets are hard. It is strongly recommended that you begin to work on them early enough. Last day/hour/minute efforts are certainly not going to bear any fruit.
No need to submit
Latex template for solutions