CS5200: Approximation Algorithms, Spring 2019

Most of the course announcements including lecture notes, and assignments will be sent over email to registered students. Scroll to the end of this page for other supplementary information.


Lecture timings: Tuesdays 2:30pm-4pm, Fridays 4pm-5:30pm (R slot).
Location: A 117
First meeting: Friday Jan 4.
Instructor: Rakesh Venkat
Office Hours: Tues 4:15pm-5:30pm (after class), C-208/C.

Announcements


Evaluation

There will be around 4-5 assignments, roughly evenly spaced, through the course. You are encouraged to spend a significant amount of time on them to gain a better understanding of the material, and also to help prepare for the quizzes and the endsem.

I will follow a zero tolerance policy towards plagiarism. If detected in any form, a direct FR grade will be awarded to the participant.

Assignments

Lectures


Course description

Many combinatorial optimization problems that arise in real-world situations are NP-hard. Consequently, we do not expect to be able to come up with efficient algorithms that find optimal solutions to these problems. The area of approximation algorithms deals with the design of efficient algorithms that output a solution which is guaranteed to be close to the optimal solution.

This course will familiarize you with various techniques used in the design and analysis of such approximation algorithms. A significant part of the course will focus on the use of Linear Programming (LP) based methods and relevant extensions, which have emerged as fundamental tools in the design of algorithms.

The course will focus on proving mathematical guarantees on the performance of algorithms. The goal is to emphasize how this not only leads to breakthroughs in our understanding of the problems considered, but also helps design robust algorithms for a variety of problems.


Prerequisites

Undergraduate Algorithms. Familiarity with algorithms, basic probability, discrete mathematics and some linear algebra is expected. You should get a flavour of the course in the first few lectures. Contact the instructor if you are unsure of having satisfied the requirements.


Suggested References

This list will be updated with time to include auxillary references to papers or other notes.