Approximation Algorithms
An approximation algorithm runs in polynomial time and returns a solution provably close to optimal for a hard optimization problem.
The tradeoff
When a problem is NP-hard, computing the exact optimum efficiently is out of reach. An approximation algorithm gives up exactness in exchange for speed, returning a solution guaranteed to be within a known factor of the best possible, in polynomial time.
Approximation ratio
The quality of an approximation is measured by its ratio: the worst-case bound on how far its output can be from optimal. A 2-approximation for a minimization problem never returns a solution more than twice the optimum. Smaller ratios mean tighter guarantees.
A worked example: vertex cover
A simple 2-approximation for minimum vertex cover repeatedly picks an uncovered edge and adds both its endpoints. The chosen edges share no vertices, so the optimum must include at least one endpoint of each; taking both at most doubles the count. Fast, and provably within a factor of two.
The landscape of approximability
- Some problems admit a PTAS: any ratio 1 + epsilon you want, at a time cost that grows as epsilon shrinks
- Some have a fixed best constant ratio and no better, unless P equals NP
- Some cannot be approximated to any constant factor unless P equals NP
Hardness of approximation
A striking branch of complexity theory proves lower bounds on approximation itself. The PCP theorem shows that for some problems, even getting close to optimal is NP-hard. So approximation is not always a free escape hatch; the difficulty can persist into the approximate version.
Guarantees versus heuristics
Approximation algorithms differ from heuristics in one crucial way: they carry a proven worst-case guarantee. A heuristic may perform better on average but can fail badly with no bound. When you need a promise about quality, an approximation algorithm provides it.