Lecture Notes on Approximation Algorithms


A first course on approximation algorithms taught at Dartmouth; I usually teach 27 of these lectures.

  1. Introduction to Approximation Algorithms
  2. Greedy Approximation Algorithm for Set Cover
  3. Greedy Approximation Algorithm for Facility Location
  4. Greedy Approximation Algorithms and Submodularity
  5. Double Greedy Approximation Algorithm for Unconstrained Submodular Function Maximization
  6. Local Search Algorithms for Max Cut and Max Coverage
  7. Non Ob(li)vious Local Search for Max 2SAT
  8. Local Search for Facility Location
  9. Local Search for k-Median
  10. Polynomial Time Approximation Scheme for Load Balancing
  11. Linear Programming Relaxations for Vertex Cover
  12. Crash Course in Linear Programming I
  13. Deterministic Rounding : Matchings in Uniform Hypergraphs
  14. Deterministic Rounding : Bipartite Matching and GAP
  15. Deterministic Rounding : Pipage Rounding
  16. Deterministic Rounding : 4-approximation for Facility Location
  17. Deterministic Rounding : k-Median
  18. Randomized Rounding : Set Cover and Independent Set
  19. Randomized Rounding : Vertex Cover in k-Partite Hypergraphs
  20. Randomized Rounding : Max SAT
  21. Randomized Rounding : Congestion Minimization
  22. Crash Course in Linear Programming II : The Dual
  23. Using the Dual : Set Cover and Vertex Cover
  24. Using the Dual : Facility Location
  25. Using the Dual : Steiner Forest
  26. Using the Dual : Approximately Solving Covering LPs
  27. Ellipsoid Algorithms and LPs with lots of constraints
  28. Cut Problems : s,t-cut and Multiway Cut
  29. Cut Problems : two algorithms for multicut
  30. Cut Problems : Uniform Sparsest Cut
  31. Cut Problems : Generalized Sparsest Cut
  32. Cut Problems : Bourgain's Embedding via Padded Decompositions
  33. Semidefinite Programming
  34. SDP : Goemans-Williamson Algorithm for Max Cut
  35. SDP : Karger-Motwani-Sudan for coloring 3-colorable graphs