Main

Advanced Algorithms

AY 2024-25, Sem II

co-taught with Prof Manoj Gupta

A link to the materials from the second half of the course will be shared here shortly.

About the Course

This course will be an exploration of approximation algorithms, focusing on techniques designed to find near-optimal solutions to computationally hard problems. Students will learn how to analyze the performance of these algorithms and apply them to various practical problems in computer science and operations research. This is one kind of coping strategy for problems that are theoretically hard. See here for an overview of other algorithmic paradigms in this context.

We will introduce the approximation paradigm with a motivating example (Load Balancing). We will then focus on a numbe rof LP-based methods for various problems, including Vertex Cover, Set Cover, Facility Location, Steiner Forest, Multiway Cut, Bin Packing, and so on. After getting familiar with encoding problems as linear programs, we will learn about deterministic and randomized rounding methods for deriving approximate solutions efficiently. We will also learn about primal-dual based approximation algorithms. Finally, we will introduce approximation schemes (in the context of Knapsack) and SDP-based methods (for maximum cut).

Problems: Load Balancing • Vertex Cover • Knapsack • Bin Packing • Set Cover • Multiway Cut • Steiner Forest • Facility Location • Traveling Salesman

Techniques: LP • SDP • Randomized Rounding • Primal-Dual • PTASes

Target Audience

This course is aimed at students interested in modern methods in the design and analysis of algorithms with a predominantly theoretical perspective.

Pre-requisites

We expect learners to be familiar with topics typically taught in an introductory discrete math course (especially graphs, discrete probability, and linear algebra), and elementary algorithm design techniques.

References

The Design of Approximation Algorithms by David P. Williamson and David B.Shmoys
Approximation Algorithms by Vijay V Vazirani

Timings and Venue

Mondays and Thursdays, 11.30AM, 11/206

Registration & Evaluation Logistics

Please register as usual through IMS. This course will have materials posted to this website, but assessments will be managed through Gradescope and announcements will be made over Google Classroom.

All assessments will be processed through Gradescope, and will use the enrolment code 3RVXNG. You will be able to add yourself as a student.

New users: If you don’t have a Gradescope account yet, go to the Gradescope website, click Sign Up in the upper right corner, select Student, and put in your entry code in the sign-up form. If the entry code doesn’t work, please email me for details on how to access the course.

Existing users: If you already have a Gradescope account, log into that account and navigate to your Account Dashboard by clicking the Gradescope logo in the top left, and click Add Course in the bottom right corner. Then enter your course code. you will be able to add yourself as a student.

For announcements, please enroll on Google Classroom via this link or via code qrquvxi.

Grading Policy

The first part of the course accounts for 50% of your total marks in the course.

There will be 12 worksheets in this course, each associated with a lecture. Each worksheet will be released at 7PM on the day of the lecture (on Gradescope), and will be due within 24 hours, i.e, 7PM on the next day. Exceptions may be made for circumstances that are beyond your control, please email me if you need an extension.

Each worksheet is worth 5 marks. Your total marks from worksheets will be scaled to 40% of your total marks (note that this is not capping: for example, if you score 30/60 from the worksheets, your total marks will be 20/40, and your final score from the worksheets will be 40/40 if and only if you earn a total of 60 points across all worksheets).

There will also be a mid-term exam worth 10 points. The format of the exam will be shared shortly.

Course Plan:

Lec #	Date	Topic	Problem Set	Slides	Lecture	Notes
1	6 Jan	Introduction to Approximation Algorithms Example: Load Balancing	W01	PDF	YT	TBA
2	9 Jan	Introduction to Linear Programming Example: Vertex Cover	on Gradescope	PDF	YT^[1]	TBA
3	13 Jan	Adaptive rounding Example: Bin Packing	on Gradescope	PDF	Part 1 Part 2	TBA
NA	16 Jan	Worksheet Discussion
4	20 Jan	Randomized Rounding Example: Set Cover	on Gradescope	PDF	YT	TBA
5	23 Jan	Randomized Rounding Example: Multiway Cut
6	27 Jan	Primal-Dual Approximation Vertex Cover Again
NA	30 Jan	Worksheet Discussion
7	3 Feb	Primal-Dual Approximation Steiner Forest
8	6 Feb	Primal-Dual Approximation Facility Location
9	10 Feb	Approximation Schemes Knapsack
NA	13 Feb	Worksheet Discussion
10	17 Feb	Approximation Schemes Traveling Salesman
11	20 Feb	Semi-Definite Programming Maximum Cut
12	24 Feb	Semi-Definite Programming Maximum Cut (contd)
NA	27 Feb	Worksheet Discussion

Sorry about choppy audio! ↩︎