When good enough is provable
For many hard problems we cannot afford the exact optimum, yet we still want a guarantee on quality. An approximation algorithm runs quickly and returns an answer with a proven bound on how far it can stray from the best possible.
The approximation ratio
The promise is captured by an approximation ratio. For a minimization problem, a ratio of two means the algorithm never returns more than twice the optimal cost, no matter the input. The smaller the ratio, the tighter the guarantee. This is stronger than a heuristic, which offers speed but no promise.
A concrete example
Consider covering a set with as few subsets as possible, the set cover problem. A simple greedy rule, always pick the subset covering the most still uncovered elements, yields a solution provably close to optimal, with a ratio that grows only slowly with the size of the universe.
Knowing the limits
Some problems admit a ratio as close to one as you like; others have a proven barrier below which no efficient algorithm can go unless P equals NP. Knowing that boundary tells you how much quality you can hope to buy with fast computation.
Key idea
An approximation algorithm trades exactness for speed while guaranteeing the answer stays within a proven ratio of the optimum.