CS6841: Approximation Algorithms, Jan-May 2018

Lecturer: Ravishankar Krishnaswamy
TAs:

Location: CS34, W 2:00-3:15; Th 3:25-5:30

Announcements


Homeworks


Completed Lectures, and Tentative Outline

In the first part of the course, we plan to look at basic covering/packing problems such as vertex cover, set cover, and minimum congestion routing. From the technical side, 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. In the second 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. In the final 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.

Student Presentations

This involves reading classical papers. 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) complete proofs or concise proof ideas. The presentations are to be 20 minutes long.
Thanks to Anupam Gupta for webpage design, and scribe template.