CS5200: Approximation Algorithms

CS5200: Approximation Algorithms, Spring 2020

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: Mondays 4pm - 5:30pm, Thursdays 2:30pm-4pm (Q slot).
Location: C LH5
First meeting: Monday Jan 6.
Instructor: Rakesh Venkat

Announcements

No class on 13/01 and 16/01. Make-up class to be scheduled soon.
We will use Piazza for all course-related discussion. All registered students are expected to enroll and check the discussions page for any announcements. Enrollment code will be given in class on 20/01. To join: search for IIT Hyderabad >> CS5200 >> enter access code, and your IIT-H email ID.

Evaluation (Tentative)

Quizzes: 4 x 15 = 60
Endsem: 40

Please note that the above evaluation plan is tentative; and there may be slight changes depending on the final class strength after the drop deadline. Possible changes include project presentations and weightage for assignments (~20).
I will follow a zero tolerance policy towards plagiarism. If detected in any form, a direct FR grade will be awarded to the participant.

Problem Sets

Homework 1, Posted: 18th Jan. Deadline: TBA.

Lectures

06/01: Lecture 1: Introduction to the course. NP-Hardness, Reductions. 2-approx for Vertex Cover.
09/01: Lecture 2: Christofides algorithm for metric TSP.
No class on 13/01 and 16/01
20/01: Lecture 3: Set Cover, Job Scheduling (Greedy Algorithms)
23/01: Lecture 4: Local Search

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.

In the last one-third of the course, we will focus on other models of algorithms such as online and streaming algorithms, and possibly techniques to prove lower bounds on the performance of algorithms.

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.

[WS] The Design of Approximation Algorithms by Williamson and Shmoys. This will be our main textbook for the course. A draft e-copy is available freely on the website of the book for personal use.
[VV] Approximation Algorithms , by Vijay Vazirani. This will serve as a good secondary reference.