Approximation Algorithms

• Lec 1 (15/03).  Introduction [WS11,KL22]
  Notation and Setup; Illustrative Examples: 2-Approximation Greedy Algorithm for Vertex Cover, Dynamic Programming based FPTAS for Knapsack, Scale and Round

• Lec 2 (22/03).  Graph Partitioning [Vaz01,KL22]
  Cut Problems: min s-t Cut, Global Min Cut, Multiway Cut, Multicut, min k-Cut, Sparsest Cut, b-Balanced Cut;  Sparsity, Conuctance and Expansion; Applications of Graph Partitioning

• Lec 3 (23/03).  LP Based Algorithm Design  [Mat15,KL22]
  min s-t Cut: LP Formulation, Rounding via Line Embedding and Sweep Cuts, Max Flow-Min Cut Theorem,min cut polytope; Cut Metric LP Relaxation

• Lec 4 (29/03).  LP Rounding  [Vaz01, WS11]
  Vertex Cover: 2-Approximation LP Rounding Algorithm, Integrality Gap Construction, Half Inegrality and Applications; MIS Problem: 2√𝑚 Approximation, Randomized Rounding 

• Lec 5 (06/04). Multiway Cut  [Vaz01,KL22]
  Isolating Cut Heuristic: 2(1-1/k)-approximation algorithm, Tight Example; LP Relaxation: min s-t cut Compact LP

• Lec 6 (26/04). LP Relaxations for Multiway Cut  [Vaz01,KL22]
  Review of Multiway Cut,  Multiway Cut Compact LP: (2-1/k) Rounding Algorithm, Integrality Gap Example, Connections to Metric LP Relaxation

• Lec 7 (03/05). CKR Algorithmfor Multiway Cut  [Vaz01,KL22]
  Metric Multiway Cut LP: Analysis, Integrality Gap; CKR LP Relaxation, Geometric Interpretation for CKR LP

References

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

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

[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