| Course Outline | General Information | Study Material | Lectures (classwise) | Assignment |
The course will consist of approximately 45 hours of lectures spread over approximately 30 meeetings
The basic thrust of the course would be to make ourselves abreast with new techniques and advanced topics in approximation algorithms.
We will try to stick to the basic course outline as given here, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Mathematics courses and have some knowledge of elementary discrete probability and linear algebra.
| Class Timings: | The schedule and coverage of the first 9 lectures are given here. The first lecture on September 29, 2015 starts at 5 pm. The venue is the 6th floor seminar room, ACM Unit, PJA Building. |
| The necessary evil - marks, exam, etc.: | -- |
| Books |
(B1) Understanding and Using Linear Programming Jiří Matoušek and Bernd Gärtner Springer (B2) Linear Programming -- Foundations and Extensions Robert J. Vanderbei Springer (B3) Combinatorial Optimization -- Algorithms and Complexity Christos H. Papadimitriou and Kenneth Steiglitz Dover Publications (B4) Linear and Non-linear Programming David G. Luenberger and Yinyu Ye Springer (B5) Linear Programming Vašek Chvátal W. H. Freeman & Co. Ltd. (B6) Linear Algebra Jin Ho Kwak & Sungpyo Hong Birkhäuser (B7)Approximation Algorithms Vijay V. Vazirani Springer (B8)The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Cambridge This book has a web version. (B9) Geometric Approximation Algorithms Sariel Har-Peled American Mathematical Society (B10) Approximation Algorithms and Semidefinite Programming Bernd Gärtner and Jiří Matoušek Springer |
| Web Resources | (W1) MIT OCW on Optimization Methods |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (29-09-2015) |
Introduction -- I | - | -- |
| Lecture 2 (30-09-2015) |
Introduction -- II | - | -- |
| Lecture 3 (01-10-2015) |
Introduction -- III | - | -- |
| Lecture 4 (05-10-2015) |
- | -- | |
| Lecture 5 (07-10-2015) |
- | -- | |
| Lecture 6 (08-10-2015) |
- | -- | |
| Lecture 7 (27-10-2015) |
- | -- | |
| Lecture 8 (28-10-2015) |
- | -- | |
| Lecture 9 (29-10-2015) |
- | -- |