main page — CS 627 Advanced Algorithms
Unit 10: Approximation Algorithms
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
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, 9:14):
Motivation & Definitions
- Video 10-2 (2025-07-08, 12:19):
Vertex Covers & Matchings
- Video 10-3 (2025-07-09, 19:45):
Greedy Set Cover
- Video 10-4 (2025-07-09, 19:42):
Layering algorithm for Set Cover
- Video 10-5 (2025-07-09, 20:25):
Shortest Superstrings via Set Cover
- Video 10-6 (2025-07-09, 21:48):
Approximation Schemes, Knapsack
- Video 10-8 (2025-07-15, 18:49):
Christofides’ TSP Algorithm
- Video 10-8 (2025-07-09, 2:31):
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.