main page — CS 627 Advanced Algorithms
Unit 10: Approximation Algorithms
This unit covers
- approximation algorithms using several examples:
- Vertex Cover
- Set Cover
- Traveling Salesperson Problem
- (F)PTAS
Material
- slides
- Video 10-1 (2025-07-08)
Motivation & Definitions
- Video 10-2 (2025-07-08)
Vertex Covers & Matchings
- Video 10-3 (2025-07-09)
Greedy Set Cover
- Video 10-4 (2025-07-09)
Layering algorithm for Set Cover
- Video 10-5 (2025-07-09)
Shortest Superstrings via Set Cover
- Video 10-6 (2025-07-09)
Approximation Schemes, Knapsack
- Video 10-8 (2025-07-09)
Randomized Approximation Algorithms
Further reading and sources
The presentation mostly follows
- Vazirani, Vijay V. “Approximation Algorithms.” Springer, 2001.
Examples are also taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.