Here is the most disciplined way to cope with an NP-hard problem: keep polynomial running time, keep every input, keep determinism — and surrender only optimality, but surrender it with a receipt. An approximation algorithm returns a solution together with a mathematical promise: "this answer is never worse than a factor \rho away from the true optimum, on any input, guaranteed." That receipt is what makes approximation a science rather than a collection of hopeful hacks.

The remarkable thing is how good and how simple these guarantees can be. A three-line greedy pairing solves Vertex Cover to within a factor of two. Doubling a minimum spanning tree gives a travelling-salesman tour at most twice optimal. And each proof follows the same beautiful template: bound your algorithm's cost against a quantity you can show is a bound on the optimum you never computed.

The approximation ratio

Fix an optimisation problem and an instance I. Let \text{ALG}(I) be the value your algorithm returns and \text{OPT}(I) the true optimum. For a minimisation problem the algorithm is a \rho-approximation (a c-approximation) if

For a maximisation problem it is the mirror image: \text{ALG}(I) \ge \rho \cdot \text{OPT}(I) with \rho \le 1 (some texts flip the convention so \rho \ge 1 always — always check which). The closer \rho is to 1, the better. The key discipline: \rho is a worst-case, every-input bound. A method that is usually within 1% but occasionally 10× off is not a 1.01-approximation — its ratio is at least 10.

A 2-approximation for Vertex Cover

A vertex cover is a set of vertices touching every edge; we want the smallest one (NP-hard). The algorithm is almost insultingly simple — repeatedly grab any uncovered edge and take both its endpoints:

The edges we pick (where we take both endpoints) share no vertices — they form a maximal matching M. Now run the template. Lower bound: every one of those |M| disjoint edges must be covered by some vertex, and no single vertex covers two of them (they share none), so any cover — including the optimum — needs at least |M| vertices: \text{OPT} \ge |M|. Upper bound: we took exactly 2|M| vertices. Chain: \text{ALG} = 2|M| \le 2\,\text{OPT}. A factor-2 guarantee from a matching we found by accident.

The figure builds it in stages: the graph, then the maximal matching (thick edges), then the cover — the six matched endpoints. Here a matching of size 3 yields a cover of size 6, while the true optimum (the three degree-heavy centres) is 3. We paid exactly the factor of two the theorem allows — this instance is the algorithm's worst case, which is the honest way to see that the "2" is tight.

Metric TSP: double the spanning tree

In metric TSP the cities obey the triangle inequality (a direct hop is never longer than a detour) — the realistic case. General TSP admits no constant-factor approximation unless \text{P}=\text{NP}, but the metric version has a gorgeous 2-approximation built on the greedy minimum spanning tree:

Christofides' algorithm sharpens this to a \tfrac{3}{2}-approximation. Instead of doubling every tree edge, it adds a minimum-weight perfect matching on just the odd-degree vertices of T, producing an Eulerian graph with far less added weight; a careful argument bounds that matching by \tfrac{1}{2}\text{OPT}. For decades 3/2 was the champion for metric TSP — only very recently nudged below by a hair.

Set Cover: greedy gives a $\ln n$ guarantee

Given a universe of n elements and a family of subsets, cover everything with as few subsets as possible. The greedy rule is the obvious one: repeatedly take the set covering the most still-uncovered elements. A charging argument — each element pays for the set that first covers it, and those payments form a harmonic sum — proves the guarantee:

This is a logarithmic, not constant, ratio — it grows (slowly) with the input. That is not laziness: Set Cover genuinely cannot be approximated better than (1-o(1))\ln n unless \text{P}=\text{NP}. Greedy is essentially the best possible, a theme the hardness-of-approximation page makes precise.