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
- Quiz 1 will be held in-class on Feb 12.
- No class on 05/02 due to exam slots.
- (18/01) No classes next week (22/01 and 25/01). We will be making up for it later.
- (18/01) HW1 is out! Due on 29/01 in-class. Clarifications will be posted on Piazza and the homework pdf file may be modified to reflect this.
- 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 08/01. To join: search for IIT Hyderabad >> CS5200 >> enter access code, and your IIT-H email ID.
Evaluation
- Assignments (20)
- Quizzes: Best 3 out of 4 (45)
- Endsem (35)
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
- Homework 1 Posted: 18th Jan. Due: 29th Jan in class.
- Homework 2 Due: 26th Mar in class
- Homework 3 Posted: 9th Apr. Due: 15th Apr, in Instructor's office, by 5:30 pm.
Lectures
- 04/01: Lecture 1: Introduction to the course. NP-Hardness, Reductions. 2-approx for Vertex Cover.
- 08/01: Lecture 2: Greedy algorithm for Set-Cover.
- 11/01: Lecture 3: Local Search for Max-Cut. Intro to Min-Degree Spanning tree.
- 15/01: Lecture 4: Proofs for Min-Degree Spanning Tree Local Search.
- 19/01: Lecture 5: Linear Optimization: Examples of formulating Combinatorial Optimization problems as ILPs.
- 29/01: Lecture 6: LP relaxations and Rounding: Vertex Cover, Randomized Rounding for Set Cover.
- 01/02: Lecture 7: Integrality Gap definition. Finishing Randomized Set-Cover Rounding. Definition of Randomized Approximation Algorithms, and Probability amplification for obtaining good solutions.
- 05/02: No Class due to exam slot.
- 08/02: Lecture 8: HW-1 discussion. Geometry of Linear programming.
- 12/02: No lecture: Quiz-1
- 15/02: Lecture 9: Geometry of LP cont'd. Max-weight Bipartite Perfect matching.
- 19/02: Lecture 10: Deterministic Rounding: Facility Location.
- 22/02: No Lecture due to Elan+Nvision
- 26/02: Lecture 11: Deterministic Rounding: Facility Location (review+finishing the proof).
- 01/03: Lecture 12: Rank Arguments: Scheduling on unrelated machines.
- 05/03: Lecture 13: Randomized Rounding: MaxSat, Max-Independent Set.
- 08/03: Lecture 14: Chernoff Bounds, Congestion Minimization.
- Midsem Break, class resumes on 26 March.
- 26/03: Lecture 15: LP Duality: Introduction, Weak and Strong Duality.
- 29/03: Lecture 16: Duality: Complementary Slackness, Primal-Dual algorithms for Vertex-Cover.
- 02/04: Lecture 17: Duality: Primal-Dual Algorithm for Feedback Vertex-Set.
- 05/04: Lecture 18: Duality: Primal-Dual Algorithm for Minimum Knapsack Problem.
- 09/04: Lecture 19: Cuts and Metrics: Multiway-Cut Problem.
- 12/04: Lecture 20: Finishing Multiway-Cut analysis.
- 16/04: Lecture 21: Buy-At-Bulk Network Design problem.
- 23/04: Lecture 22: SDP for Max-Cut, Goemans-Williamson algorithm.
- 26/04: Quiz-4
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.