Approximation Algorithms I @ Northwestern

Tentative syllabus for Fall 2024

Combinatorial Algorithms

  • Travel Salesperson Problem (the Christofides 3/2-approximation algorithm).
  • Set Cover (log n approximation).
  • Knapsack (2 approximation and PTAS).
  • Bin Packing (2 approximation and PTAS).
  • Knapsack (2 approximation and PTAS).
  • Bin Packing (2 approximation and PTAS).

Scheduling

  • Makespan Scheduling on identical machines (4/3 approximation and PTAS).
  • Scheduling with precedence constraints (Graham’s 2-approximation algorithm).

Clustering

  • k-center (2 approximation).
  • k-means. Lloyd’s algorithm.
  • k-means++ (O(log k) approximation).
  • Correlation Clustering (3 approximation).
  • Local Search. k-median (5 approximation).

Linear Programming Based Algorithms

  • Set Cover.
  • Vertex Cover.
  • LP Duality. Examples. Min s-t Cut/Max Flow.
  • Integrality of min s-t cuts.
  • Multiway Cut (2 & 1.5 approximations)
  • Multicut (log n approximation).
  • Padded Decomposition.
  • Embeddings into Trees & Random Trees. Applications.
  • Sparsest Cut. Balanced Cut. LP Relaxation for the problems.
  • Embeddings into L1. O(log n) approximation for Sparsest Cut.
  • Graph Laplacian. Cheeger’s Inequality.

Semidefinite Programming Based Algorithms

  • Max Cut.
  • Coloring. Combinatorial Algorithm. SDP algorithm.
  • SDP Relaxation for Sparsest Cut.