CS6841: Approximation Algorithms, Jan-May 2017

Lecturers: N.S. Narayanaswamy, Ravishankar Krishnaswamy
TAs: Dhanyya, Sharmili Murthy

Location: CS27, W 2:00-2:50; F 2:00-4:30



Completed Lectures, and Tentative Outline

In the first part of the course, we plan to look at basic covering/packing problems such as set cover, max-k-coverage, and submodular maximization. For each of these problems, we will cover various algorithmic techniques (greedy, local search, primal-dual, LP rounding) which have different quality of approximation guarantees depending on the type of input instances. Then we will delve into the limitations of these algorithms. Finally, we will discuss the inherent hardness in getting any approximation algorithms for these problems, under standard complexity assumptions. In the second part, we will follow the same template for graph partitioning problems such as min cut, max cut, multi-cut, and sparsest cut. The techniques now additionally include SDP rounding and metric embeddings. In the third part, we will focus on resource allocation problems, such as max-min allocation, min-max allocation, and bin packing. Now the techniques will include designing PTASs, and rounding so-called configuration LPs, in addition to the ones described above.

Student Presentations

This involves reading papers from other areas of computer science where the underlying problem tackled is related to some of the problems studied in this course. The overall goal is to get a sense of how real world problems are abstracted as crisp algorithms questions, and how their (exact or approximate) solutions are deployed back in the real world. Students are expected to form groups of two, choose a paper, and present (a) the goal of the paper, (b) the underlying problem, (c) the solution provided in the paper, and (d) any other algorithms based on topics covered in class which might be applicable. The presentations are to be 20 minutes long.
Thanks to Anupam Gupta for webpage design, and scribe template.