- Linear Programming Duality
- This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.
- Steiner Forest and Primal-Dual Approximation Algorithms
- This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem.
- Facility Location and Primal-Dual Approximation Algorithms
- This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem.
- Maximum Cut and Semi-Definite Programming
- We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.
