COURSE INFO:

Instructor: Amey Bhangale

Time and Place: Tuesdays and Thursdays 5pm - 6:20pm (via Zoom)

Office Hours: Wednesday 2-4pm

Prerequisites: Basic algorithms, some discrete probability and mathematical maturity.

OBJECTIVE:

There are many optimization problems where finding an optimal solution is NP-hard. For many such problems, one can design efficient algorithms that always give a solution that is "not very far" from the optimal solution. Such algorithms are call approximation algorithms.

The main objective of this seminar course is to learn interesting approximation algorithms. We start with some basic approximation algorithms and then move to more advanced ones. These include algorithms that use off-the-shelf solvers used to solve linear programs/ semi-definite programs.

TOPICS : This is a graduate course on approximation algorithms. Topics may include:

- Basic complexity classes P, NP

- Introduction to Approximation algorithms

- Linear Programming and applications

- Set Cover, Vertex Cover

- Duality of LP

- Facility location

- Sparsest Cut (l1 embedding)

- Semidefinite programming, Ellipsoid Method

- Constraint satisfaction problems (CSPs)

- Max-Cut approximation algorithm

- Graph coloring algorithms

- Multiplicative weights Update

- Hardness of approximation

There will be 3 homework. We'll either have paper presentations at the end, or a final take-home exam.

REQUIRED MATERIALS:

This course will mostly be self-contained (mostly presenting algorithms directly from the research papers)

However, you might find the following two books helpful:

1. Approximation Algorithms by Vijay V. Vazirani

2. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys