Approximation algorithms are polynomial-time procedures for NP-hard optimization problems that guarantee solutions within a provable factor of optimal β the approximation ratio (or performance guarantee). Unlike exact solvers, they trade optimality for tractability, making previously infeasible problems solvable at scale. Heuristics such as simulated annealing and genetic algorithms complement theoretical approximations by performing excellently in practice without worst-case guarantees. The field sits at the intersection of algorithm design, combinatorial optimization, and complexity theory, with results ranging from simple greedy analyses to deep LP-rounding and semidefinite programming machinery.
What This Cheat Sheet Covers
This topic spans 15 focused tables and 70 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Approximation Complexity Classes
The hierarchy P β FPTAS β PTAS β APX β NPO classifies how well NP-hard problems can be approximated in polynomial time. Understanding where a problem falls determines which algorithm design techniques are available and what hardness barriers exist.
| Technique | Example | Description |
|---|---|---|
0-1 Knapsack# poly in n and 1/Ξ΅ | Achieves (1+\varepsilon)-approximation in time poly in both n and 1/\varepsilon;β’ strongest class beyond P β’ only weakly NP-hard problems admit FPTAS | |
Euclidean TSPMakespan scheduling | For every fixed \varepsilon>0 returns (1+\varepsilon)-optimal solution in n^{f(1/\varepsilon)} time;β’ running time may be exponential in 1/\varepsilonβ’ strictly contains FPTAS | |
Metric TSPVertex CoverMax-3SAT | Admits a constant-ratio polynomial approximation; β’ APX-hard problems have no PTAS unless P=NP β’ PCP theorem underlies hardness |