VII · Computational complexity
Approximation algorithms
What it is
When exact solutions are too expensive, find an answer guaranteed within a factor of optimal. PTAS: arbitrarily close. APX: bounded ratio.
Where it lives
Set cover, bin packing, MAX-SAT, scheduling. Production solvers routinely use 1.5×-optimal as "good enough".
The key insight
Some problems have no constant-factor approximation unless P = NP (max independent set). Some have a PTAS (knapsack). The classification matters.