Randomized and Approximation Algorithms (M.Tech CS, 2020)

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:

      • Chapter 8 from [DPU17]

      • Chapter 8 from [KT06]

      • Chapter 9 from [P94]

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:

      • Chapter 8 from [DPU17]

      • Chapter 8 from [KT06]

      • Chapter 9 from [P94]

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:

      • Section 14.1 in Chapter 14 from [V03]

      • Chapter 1 from [WS11]

      • Section 3.2 in Chapter 3 from [V03]

      • Section 2.4 in Chapter 2 from [WS11]

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:

      • Section 2.4 in Chapter 2 from [WS11]

      • Section 3.2 in Chapter 3 from [V03]

      • Chapter 6 from [MG07]

      • Chapter 12 from [V03]

Topics covered: 29 April'21

  • Totally Unimodular matrices and their application to ILP

  • Complementary slackness conditions with applications to Max-Flow problem

  • Readings:

      • Section 8.2 in Chapter 8 from [MG07]

      • Chapter 12 from [V03]

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:

      • Chapter 1 from [MU17]

      • Chapter 1 from [MR95]

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:

      • Sections 6.1 and 6.2 from [MU17]

      • Section 1.1 in Chapter 1 from [AS16]

      • Sections 2.1, 2.2, and 2.4 in Chapter 2 from [AS16]

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:

      • Section 6.4 in Chapter 6 from [MU17]

      • Section 3.2 in Chapter 3 from [AS16]

      • Turan's Theorem (Page 100) from [AS16]

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:

      • Section 6.5 in Chapter 6 from [MU17]

      • Section 4.4 in Chapter 4 from [AS16]

      • Erdos-Ko-Rado Theorem (Page 18) from [AS16]

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:

      • Sections 6.6 and 6.7 in Chapter 6 from [MU17]

      • Section 5.1 in Chapter 5 from [AS16]

Topics covered: 8 July'21

  • Asymmetric Lovász local lemma

  • Non-constructive proof of Asymmetric Lovász local lemma

  • Readings:

      • Sections 6.7 and 6.9 in Chapter 6 from [MU17]

      • Section 5.1 in Chapter 5 from [AS16]

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:

      • Lectures 1, 8, and 9 from [EGT]

      • Read "Turan Numbers and Dependent Random Choice", pages 317 - 319, from [AS16]