Randomized and Approximation Algorithms (M.Tech CS, 2020-21)
Randomized and Approximation Algorithms (M.Tech CS, 2020-21)
Instructor Arijit Bishnu and Arijit Ghosh
Description In this course we will cover various topics in Randomized and Approximation Algorithms
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences.
Class timings Tuesday 4:30 - 6:30 pm and Thursday 2:30 - 4:30 pm
Syllabus
NP, NP-completeness, Reduction
Approximation Algorithms
Randomized Algorithm
The Probabilistic Method
References
[AB09] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016.
[DPU17] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, Algorithms, McGraw Hill Education, 2017.
[EGT] David Conlon, Lecture Notes on Extremal Graph Theory, Oxford University.
[F99] Ehud Friedgut, Sharp thresholds of graph properties and the k-SAT problem, Journal of the American Mathematical Society, 12 (4): 1017–1054, 1999.
[FS11] Jacob Fox and Benny Sudakov, Dependent Random Choice, Random Structures & Algorithms, 38(1-2): 68–99, 2011.
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.
[KT06] Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2006.
[MG07] Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, Springer, 2007.
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[MU17] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Second Edition, Cambridge University Press, 2017.
[P94] Christos Papadimitriou, Computational Complexity, Pearson, 1994.
[R19] Thomas Rothvoss, Probabilistic Combinatorics, Graduate Topics Course in Mathematics, UW Seattle, Winter 2019.
[V03] Vijay Vazirani, Approximation Algorithms, Springer, 2003.
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
[HP11] Sariel Har-Peled, Geometric Approximation Algorithms, AMS, 2011. (Preliminary version)
[HP18] Sariel Har-Peled, Randomized Algorithms, Lecture notes, UIUC, 2018.
Lecture details
Topics covered: 1 April'21
NP, NP-completeness, Reduction
Readings:
Topics covered: 6 April'21
NP-completeness of Hamiltonian cycle via reduction from SAT
NP-completeness of Set cover (SC) via reduction from Vertex cover (VC) problem
Introduction to the class co-NP
Readings:
Topics covered: 8 April'21
Introduction to Linear Programming (LP) and Integer Linear Programming (ILP)
Examples of LPs and ILPs
2-factor approximation to VC problem via maximal matching
2-factor approximation to VC problem via ILP and rounding
Readings:
Chapter 3 from [MG07]
Topics covered: 13 April'21
f-factor approximation algorithm for SC problem
2-factor approximation for Bin packing problem
Inapproximability of the general Travelling Salesman Problem (TSP)
2-factor approximation algorithm for Euclidean TSP
Readings:
Topics covered: 15 April'21
3/2-factor approximation algorithm for Euclidean TSP
Introduction to LP duality
Strong and Weak duality theorems for LP
Readings:
Topics covered: 29 April'21
Totally Unimodular matrices and their application to ILP
Complementary slackness conditions with applications to Max-Flow problem
Readings:
Topics covered: 6 May'21
Introduction to Dynamic programming (DP) and
Examples of DP: LCS, Longest Increasing sequence, Matrix multiplication, All-Pair Shortest Paths, and Knapsack Problem
Readings:
Topics covered: 8 May'21
Definitions of PTAS and FPTAS,
Modified Dynamic program for Knapsack problem
FPTAS for Knapsack problem
Introduction to the class “strong NP” and some related results
Readings:
Chapter 8 from [V03]
Topics covered: 11 May'21
Introduction to Randomized algorithms
Randomized Quicksort and its analysis,
Randomized Minimum cut algorithm via edge contraction
Counting number of Minimum cuts using the analysis of the above algorithm
Readings:
Topics covered: 15 June'21
Introduction
Ramsey number R(k,l)
Lower bound for R(k,k) using the probabilistic method
Existence of large cuts in graphs
Balancing vectors
Readings:
Topics covered: 22 June'21
Introduction to alteration technique
Large independent sets in graphs via alteration
Introduction to Erdos–Renyi random graphs
Existence of graphs with large girth and many edges via random graphs and alteration
Turan's theorem on independent sets in graphs via random permutation
Readings:
Topics covered: 29 June'21
Erdos-Ko-Rado Theorem and its proof via random permutation
Second Moment Method
Threshold behaviour in random graphs
Threshold
Readings:
Topics covered: 1 July'21
Conditional Expectation Inequality
Threshold behaviour in random graphs using conditional expectation inequality
Statement of General Lovasz Local Lemma
Proof of Symmetric Local Lemma using the general case
Readings:
Topics covered: 8 July'21
Asymmetric Lovász local lemma
Non-constructive proof of Asymmetric Lovász local lemma
Readings:
Topics covered: 10 July'21
A brief introduction to Extremal Graph Theory
Mantel's Theorem
Turán's Theorem
Kővári, Sós, and Turán Theorem
Construction of 4-cycle free graphs with many edges using algebraic/geometric techniques
Readings:
Lectures 1 and 8 from [EGT]
Topics covered: 17 July'21
Revisiting the construction of 4-cycle free graphs with many edges using algebraic/geometric construction
Almost matching lower bound to Kővári, Sós, and Turán Theorem using random graphs and alteration technique
Dependent random choice and Turán numbers of a bipartite graph
Readings: