- Vertex cover and Linear Programming
- We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques.
- Knapsack and Rounding
- This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem.
- Bin Packing, Linear Programming and Rounding
- This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)
- Set Cover and Randomized Rounding
- This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem.
- Multiway Cut and Randomized Rounding
- This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem. (This is a more advanced module.)