CS6841: Approximation Algorithms, Jan-May 2021

Lecturer: Ravishankar Krishnaswamy

TAs: Anil and Girish

Location: C Slot On Google Meet

Announcements

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

Completed Lectures (handwritten notes of all notes)

• (01/02/2021). Course Introduction.
  • Introduced approximation algorithms and explained why we study them. Saw Johnson's Algorithm for Max-3-SAT.


• (02/02/2021). Useful Probability (handwritten notes).
  • Introduced basic probabilistic tools useful in this course and elsewhere.


• (03/02/2021,05/02/2021). Linear Programming (handwritten notes).
  • Introduced linear programming and exlained their utility.
  • Covered Basic Feasible Solutions and Duality.


• (08/02/2021-16/02/2021). The Set Cover Problem (handwritten notes).
  • Introduced this fundamental problem, and showed an f-approximation by solving the LP, and also an `Primal Dual` f-approximation which does not need to solve the LP.
  • Showed a O(log n)-approximation using Randomized Rounding.
  • Analyzed the greedy algorithm for the problem to show a O(log n) approximation.
  • Presented an improved `dual fitting' analysis of the greedy algorithm.
  • Introducted th classical discrepancy problem to illustrate the power of Linear Programming BFS.


• (17/02/2021-19/02/2021) The Knapsack Problem (handwritten notes).
  • Introducted this classical problem to illustrate the concept of PTAS, and the Dynamic Programming + Discretization approach.
  • Finished the Discretization+DP-based FPTAS for Knapsack.


• (22/02/2021-05/03/2021) Machine Scheduling/Load Balancing (handwritten notes).
  • Introducted this classical problem of minimizing makespan on identical machines to illustrate the greedy algorithm (which incidentally is an "online algorithm"), and started working towards a PTAS.
  • Covered the ideas of guessing OPT and enumerating small instances to get PTAS for Makespan on identical machines.
  • Introduced the ``unrelated machines scheduling'' problem and covered the natural LP relaxation.
  • Covered the 2-approximation by solving the LP to find a BFS, followed by a tree-rounding.
  • Covered another 2-approximation algorithm using the concept of ``iterative rounding''.
  • Introduced and Proved Holder's Inequality for use in understanding l_p norms.
  • Presented an online algorithm for Makespan on Unrelated Machines using a greedy algorithm on a l_p norm soft-max potential function.


• (08/03/2021-26/03/2021) Clustering (handwritten notes).
  • Introduced metric spaces, and the clustering problems.
  • Presented the 2-approximation for the k-Center objective.
  • Introduced the k-Median Objective and presented an LP relaxation for it.
  • Presented the LP-rounding based 4-approximation which opens 2k centers instead of k (bi-criteria approximation algorithm).
  • Presented a more involved dependant rounding idea which only opens k centers and has O(1)-approximation.
  • Covered a primal-dual 3-approximation for the related facility location problem.
  • Using this, we covered a 6-approximation for the k-median by using the Lagrangean Relaxation technique.


• (05/04/2021-16/04/2021) Dimension Reduction, Locality Sensitive Hashing (handwritten notes).
  • Introducted the Gaussian Random Variable and studied some useful properties of Gaussian vectors.
  • Introducted the dimension reduction problem, and saw how Gaussian projections can preserve distances approximately.
  • Introduced the Near-Neighbor Search problem and saw how a Locality Sensitive Hashing scheme and effeciently sovle it.
  • Studied good LSH schemes for the Hamming distance metric.


• (19/04/2021-23/04/2021) Max-Cut and Semidefinite Programming (handwritten notes).
  • Studied a simple LP rounding for min cut.
  • Saw how to model max-cut using a linear programming with infinitely many constraints, which is equivalent to SDP.
  • Briefly saw the connection between these infinite linear constraints, vector inner-products and non-negative eigenvalues and used this connection to solve the SDP with the Ellipsoid method.
  • Saw a simple rounding scheme (using connections to the LSH!) which converts vectors to bits and analyzed its performance.


• (27/04/2021-30/04/2021) Differential Privacy (handwritten notes).
  • How do we model what it is to do data analysis while protecting individual privacy?
  • Motivated the model of Differential Privacy and formally defined it. Saw how we intentionally add noise (and approximations) to preserve the privacy!
  • Analyzed the Laplacian Mechanism for count queries and also the exponential mechanism for for outputs restricted to a range.


• (03/05/2021-07/05/2021) Hardness of Approximation (handwritten notes).
  • Like we showed a problem is NP-complete to model its complexity for decision problems, how do we get a similar measure for optimization problems?
  • Introduced Gap problems as an intermediary waypoint between decision problems and optimization problems which will help in obtaining hardness of approximation for optimization problems.
  • Stated the PCP theorem and showed the beautiful connection between the PCP viewpoint and NP-completeness of Gap3SAT.
  • Introduced the LabelCover problem and outlined how we show hardness of other problems using GapLabelCover.