Intractability & Approximation
A 10-module path through intractability & approximation, in study order from foundations to the frontier.
Modules
- P and NP: Decision Problems and Verification
- Polynomial-Time Reductions
- NP-Completeness and Cook-Levin
- A Tour of Classic NP-Complete Problems
- Coping with NP-Hardness
- Approximation Algorithms and the Approximation Ratio
- A 2-Approximation for Vertex Cover
- Approximating Metric TSP
- Heuristics and Local Search
- Online Algorithms and Competitive Analysis