Approximation Algorithms

• Lecture 1.  Introduction [WS11,KL22]  Notation and Setup, Greedy Algorithm for Vertex Cover, DP based FPTAS for Knapsack, Scale and Round

• Lecture 2.  Graph Partitioning [Vaz01,KL22] Buffet of Cut Problems, Applications of Graph Partitioning

• Lecture 3.  LP Based Algorithm Design  [Mat15,KL22] min s-t Cut LP Formulation, Rounding via Line Embedding and Sweep Cuts

• Lecture 4.  LP Rounding  [Vaz01, WS11]  2-approximation LP Rounding for Vertex Cover (VC), Integrality Gap, Half Inegrality of VC, Applications

• Lecture 5.  Multiway Cut  [Vaz01,KL22] Isolating Cut Heuristic, 2(1-1/k)-approximation Algorithm, Tight Example

• Lecture 6.  LP Relaxations for Multiway Cut  [Vaz01,KL22] Multiway Cut Compact LP, (2-1/k) Rounding Algorithm, Integrality Gap Example

• Lecture 7.  CKR Algorithmfor Multiway Cut  [Vaz01,KL22] CKR LP Relaxation, Geometric Interpretation, 3/2-approximation Algorithm

• Lecture 8.  Multicut Problem [Pan19,Che21] CKR LP Relaxation, O(log k)-approximation Algorithm

• Lecture 9.  Multicut Problem contd. [Pan19,Che21] Integrality Gap Construction, Multicommodity Flow, Flow-Cut Gap

• Lecture 10.  Introduction to Expander Graphs. [Che21,Sar21,Lau22] Motivation, Conducatance of a Graph, Examples and Non-Examples

• Lecture 11.  Expander Graphs. [Che21,Sar21,Lau22] Conductance as robustness to edge deletion, Application: Sublinear time dynamic connectivity.

• Lecture 12.  Properties of Expander Graphs. [Che21,Sar21] Low diameter property, Region growing argument

• Lecture 13.  Constructions of Expander Graphs. [Sar21] Randomized constructions - G(n,p) graphs, random matchings, Deterministic constructions.

• Lecture 14.  Vertex Expansion. [Sar21] Robustness to vertex deletion, Connections to edge expansion, Low diameter property

• Lecture 15.   Expansion with general demand. [Sar21] Defining edge expansion using general demand with applications.

• Lecture 16.   Graph Connectivity. [Vaz01, Che21, Sar21, Lau22] Max Paths, Fractional Packing and Covering Problems, 

• Lecture 17.   Course Review.

References

[Che21] Course on Approximation Algorithms by Chandra Chekuri, UIUC, 2021

[KL22]  Course on Approximation Algorithms by Arindam Khan and Anand Louis, IISc, 2022

[Lau22] Notes on Eigenvalues and Polynomials by Lapchi Lau, University of Waterloo, 2022

[Mat15] Course on Approximation Algorithms by Claire Mathieu, Coursera, 2015

[Pan19] Course on Graph Algorithms by Debmalya Panigrahi, Duke University, 2019

[Sar21] Course on Expanders and Fast Graph Algorithms by Thatchaphol Saranurak, University of Michigan, 2021

[Vaz01] Approximation Algorithms by Vijay V.Vazirani, Springer-Verlag, 2001

[WS11]  The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011