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.