CS6841: IITM Approximation Algorithms, Jan-May 2017

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

Announcements

(13/1): The course evaluation will be based on roughly 5 homeworks, 1 end-sem, and 1 student presentation (which will happen in teams)
(13/1): Here are some very useful notes on probability bounds: Chernoff, Bernstein, Markov, Chebyshev.

Homeworks

Homework 1 (source file for typsetting answers) (due 10/02/2017)
Homework 2 (source file for typsetting answers) (due 10/03/2017)
Mid-Semester Course Feedback
Homework 3 (source file for typsetting answers) (due 29/03/2017)
Homework 4 (source file for typsetting answers) (due 12/04/2017)
Endsem Takehome Exam (source files for typsetting answers) (due //2017)

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.

(13/1/2017) Lecture 1 (RK). Greedy Algorithm for Set Cover and Max Coverage.
Introduced approximation algorithms as means to cope with NP-Completeness.

Presented greedy algorithm for Set Cover and Max-k-Coverage.

Introduced Submodular functions and showed how same greedy algorithm works well for maximizing monotone submodular functions.

(18/1/2017) Tutorial 1 (NSN).
Introduced the dual problem (Hitting Set).

Motivated and studied algorithms for special case instances of set cover (such as vertex cover).

(20/1/2017) Lecture 2 (RK). LP-Rounding for Set Cover.
Motivated Linear Programming as a generic framework.

Presented randomized rounding for Set Cover.

Went over bad examples which show the limits for greedy and LP rounding algorithms (rounding gap vs integrality gap).

(25/1/2017) Tutorial 2 (NSN).
Showed a factor 2-approximation for Vertex Cover by LP rounding.

Showed matching LP integrality gaps.

(27/1/2017) Lecture 3 (RK). Greedy and LP Rounding for Min-Sum Set Cover.
Presented greedy algorithm's analysis of a constant factor approximation.

Formulated an LP for the problem and showed a rounding with an O(1) factor.

Introduced a generalization and mentioned how the natural LP can have a large integrality gap.

(1/2/2017) Tutorial 3 (NSN).
Showed that Vertex Cover LP is 1/2 integral.

Defined the Feedback Vertex Set problem.

(3/2/2017) Lecture 4 (RK). The Primal-Dual Method.
Introduced duality, strong duality theorem, and complementary slackness.

Motivated the primal-dual algorithmic framework by using relaxed complementary slackness conditions.

Showed an f-approximation for Set Cover as an application.

(8/2/2017) Tutorial 4 (NSN).
Started the O(log n) algorithm for Feedback Vertex Set.

(10/2/2017) Lecture 5 (RK). The Primal-Dual Method Part 2.
Went over the primal-dual framework once more.

Studied the exact primal-dual algorithm for the minimum cost arborescence problem.

Introduced the Steiner forest problem.

(17/2/2017) Lecture 6 (RK). The Primal-Dual Method Part 3; Intro to Local Search.
Designed primal-dual algorithms for Steiner Forest.

Intro to local search with Max-k-Coverage.

Started the analysis of local search for k-median.

(22/2/2017) Tutorial 5 (NSN).
Showed simple approximation hardness reductions between some problems.

(24/2/2017) Lecture 7 (VG). Introduction to Non-approximability (Guest lecture by Venkat Guruswami).
Introduced hardness of approximation via promise problems.

Stated the PCP theorem and showed its deep connections with hardness of approximation.

Introduced the Label Cover problem and used to for Max-k-Coverage hardness 1 vs 3/4.

(3/3/2017) Lecture 8 (RK). Finished 1 vs 3/4 Hardness of Max-k-Coverage.
Recapped the Label Cover problem.

Showed the reduction from Label Cover to Max-k-Coverage.

(10/3/2017) Lecture 9 (RK). The k-Median Problem (Hardness, Local Search, Metric Embeddings).
Recapped the k-Median problem and showed the hardness reduction from Max-k-Coverage.

Introduced the notion of Metric Embeddings and showed a O(log n)-approximation using this.

Completed the analysis of the 5-approximation using local search.

(17/3/2017) Lecture 10 (RK). Semidefinite Programming (Max-Cut, Graph Colouring).
Introduced Max-Cut and saw a local search 1/2 approximation.

Motivated Quadratic Programming (and hence SDPs).

Analyzed Goemans-Williamson rounding for Max-Cut SDP.

Introduced Graph Colouring program and saw the KMS rounding algorithm for n^0.25 colouring.

(24/3/2017) Lecture 11 (RK). Sparsest Cut.
Introduced the problem and a metric relaxation.

Showed Bourgain's metric embedding theorem to get a O(log n) approximation for Sparest Cut.

While we showed a cheating proof, see here for the formal proof.

(31/3/2017) Lecture 12 (RK). Concentration bounds and applications.
Went over Markov, Chebyshev, Chernoff and Bernstein's inequalities.

Saw applications in load balancing, median-of-values for boosting, and set discrepancy.

(07/4/2017) Lecture Canceled.

(12/4/2017) Student Presentations.

(19/4/2017) Student Presentations.
End of class! Thanks for attending and participating!

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.