CS6841: IITM Approximation Algorithms, Jan-May 2018

CS6841: Approximation Algorithms, Jan-May 2018

Lecturer: Ravishankar Krishnaswamy

TAs:

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

Announcements

(13/1): The course evaluation will be based on roughly 4-5 homeworks, 1 end-sem, and 1 student presentation

Homeworks

Homework 1 (source file for typsetting answers) (due 28/02/2018)
Homework 2 (source file for typsetting answers) (due 21/03/2018)
Homework 3 (source file for typsetting answers) (due 05/04/2018)
Homework 4 (source file for typsetting answers) (due 26/04/2018)
Endsem Takehome Exam (source files for typsetting answers) (due 10/05/2018)

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.

(17/1/2018) Lecture 1 (RK). Course Introduction.
Introduced approximation algorithms and explained why we study them.

(25/1/2018) Lecture 2 (RK). Intro to Probability Inequalities.
Went over basics of probability and concentration bounds, and looked at various applications of these such as balls and bins, etc.

Introduced Vertex Cover problem and studied simple 2-approximation.

(01/2/2018) Lecture 3 (RK). Introduction to Linear Programming.
Went over basics of Linear Programming such as polytopes, basic feasible solutions, etc.

Formulated an LP for the weighted vertex cover problem and showed a rounding with 2-approximation.

(07/2/2018) Lecture 4 (RK). LP rounding for Set Cover.
Introduced the Set Cover problem and showed the f-approximation and O(log n) approximation using LP rounding.

(08/2/2018) Lecture 5 (RK). Greedy Algorithms for Set Cover.
Studied the performance of greedy algorithm for both the set cover and min-sum set cover problems.

Handwritten notes are available here.

(14/2/2018) No Class. Institute Holiday.

(15/2/2018) Lecture 6 (RK). Primal-Dual Algorithms.
Introduced the Dual of an LP and motivated Primal-Dual Algorithms.

(21/2/2018) Lecture 7 (RK). Primal-Dual Algorithms for Weighted Vertex Cover.
Showed how to use the Primal-Dual framework for 2-approximation for weighted vertex cover.

(22/2/2018) Lecture 8 (RK). Primal-Dual Algorithms Steiner Forest.
Showed how to use the Primal-Dual framework for 2-approximation for Steiner Forest.

Along the way saw a 2-approximation for the Steiner Tree problem.

Handwritten notes for past three lectures are available here.

(28/2/2018) Lecture 8 (RK). Wrapped up Steiner Forest.
Finished the proof of the Steiner Forest Primal-Dual algorithm.

(1/3/2018) Lecture 9 (RK). Local Search for k-Median.
Introduced Clustering problems and studied a 5-approximation for k-Median using Local Search.

(7/3/2018) Lecture 10 (RK). Online Algorithms I.
Introduction to Online Algorithms, and the paging problem.

(8/3/2018) Lecture 11 (RK). Class canceled.

(14/3/2018) Lecture 12 (RK). Online Algorithms II.
Studied the randomized 1-bit LRU (Marking Algorithm) for Paging.

(15/3/2018) Lecture 13 (RK). Online Algorithms III.
Studied the waterfilling algorithm for (1-1/e) competitive online matching.

(21/3/2018) Lecture 14 (RK). Online Algorithms IV.
Introduced the online learning problem and studied the multiplicative-weights algorithm.

Handwritten notes are available here.

(22/3/2018) Lecture 15 (RK). Machine Scheduling for Minimizing Makespan.
Saw the 2-approximation for Graham's list scheduling and introduced Dynamic Programming based approach for PTAS design.

Handwritten notes are available here.

(28/3/2018) PTAS Design II (RK).
Completed the PTAS for Makespan scheduling and saw PTAS for Knapsack.

(4/4/2018) Lecture 17 (RK). Intro to Stochastic Optimization.
Studied a O(1)-approximation for Stochastic Knapsack problem.

(5/4/2018) Lecture 18 (RK). Semidefinite Programming.
Introduced SDPs and saw the rounding algorithms for Max-Cut and 3-coloring.

(11/4/2018) Lecture 19 (RK). Intro to Metric Embeddings.
Defined metric embeddings, and stated Bourgain's embedding into l_1 and the Johnson-Lindenstrauss Lemma.

(12/4/2018) Lecture 20 (RK). Metric Embeddings II.
Proved Bourgains Theorem for embeddings into l_1 spaces. Defined the sparsest cut problem, and showed a O(log n) approximation using this theorem.

Handwritten notes for last two lectures are available here.

(18/4/2018) Lecture 21 (RK). Hardness of Approximation I.
Recapped NP-completeness, proof systems, and introduced the PCP class.

Handwritten notes are available here.

(19/4/2018) Lecture 22 (RK). Hardness of Approximation II.
Stated the PCP theorem, and saw implications to hardness of approximation. Defined Label Cover problem and applied it for max-coverage hardness.

(25/4/2018) Student Presentations.

(26/4/2018) Student Presentations.

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.