# Approximation Algorithms Part I

• 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.)

### Plataforma 