Approximation
algonotes
lecturenotes
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)
