Approximation

We introduce the paradigm of approximation algorithms. We study two problems this week - vertex cover and set cover, and four techniques:

• a structural approach (using maximal matchings to approximate vertex cover)
• a greedy approach (for set cover)
• deterministic rounding of linear programs (for vertex cover)
• working with dual variables (for set cover)