Proving that an optimization problem is NP-hard does not end the matter: the instances still have to be solved. One of the most solid answers the theory offers is the approximation algorithm, which runs in polynomial time and returns a solution that is not necessarily optimal but comes with a proven guarantee on its distance from the optimum. Unlike an arbitrary heuristic, the guarantee holds on every instance, even the worst one.
The approximation ratio
For a minimization problem, an algorithm is a ρ-approximation if on every instance it returns a solution costing at most ρ times the optimal cost, with ρ ≥ 1. For a maximization problem, the solution must be worth at least the optimum divided by ρ (or, in another common convention, at least ρ times the optimum with ρ ≤ 1).
The conceptual difficulty is obvious: we do not know the optimum, because computing it is NP-hard. The standard technique is to find a lower bound on the optimum that is easy to compute, and compare the solution against that bound.
Example 1: vertex cover, ratio 2
The problem: find the smallest set of nodes touching every edge of a graph.
The algorithm:
- while some edge (u, v) is uncovered, add both u and v to the solution;
- remove every edge touching u or v.
The edges chosen in step 1 share no endpoints: they form a matching. Let M be this set of edges.
- The solution has exactly 2|M| nodes.
- Every cover, including the optimal one, must contain at least one endpoint of each edge in M, and these endpoints are all distinct. So the optimum is at least |M|.
Hence: solution ≤ 2 × optimum. The lower bound is the size of the matching. It is an algorithm of a few lines with a guarantee that, surprisingly, is still the best known up to lower-order terms.
Example 2: the metric travelling salesman
The travelling salesman asks for the shortest tour visiting every city once. In the metric version distances obey the triangle inequality: going straight from A to C never costs more than going through B.
The two-step algorithm:
- compute a minimum spanning tree T;
- traverse T depth-first and list the cities in order of first visit, skipping those already seen.
Analysis:
- removing one edge from the optimal tour gives a spanning tree, so cost(T) ≤ optimum;
- walking every edge of T twice costs 2 × cost(T);
- skipping cities already seen does not lengthen the route, by the triangle inequality.
Result: a 2-approximation. Christofides' algorithm improves the ratio to 3/2 by adding a minimum-cost perfect matching on the odd-degree nodes of the tree.
Without the triangle inequality there is no hope
For the general travelling salesman, if P ≠ NP, there is no ρ-approximation for any constant ρ. The proof is a reduction from the Hamiltonian cycle problem: given a graph, assign cost 1 to the edges present and cost ρ·n + 1 to those missing. If a Hamiltonian cycle exists, the optimal tour costs n; otherwise it costs more than ρ·n. A ρ-approximation would tell the two cases apart and decide an NP-complete problem.
Example 3: knapsack and approximation schemes
Some problems admit arbitrarily good approximations. A polynomial-time approximation scheme (PTAS) is a family of algorithms that, for every ε > 0, gives a (1 + ε)-approximation in time polynomial in n, but with any dependence on ε. If the dependence on 1/ε is polynomial too, it is an FPTAS.
Knapsack has an FPTAS. The idea:
- divide the item values by a factor proportional to ε·V_max/n and round down;
- solve the rounded instance exactly with dynamic programming over values, which are now small;
- the error introduced by rounding is at most a fraction ε of the optimum.
Precision is thus traded for time in a controlled way.
The limits: inapproximability
The theory says not only what can be approximated but also what cannot. The central tool is the PCP theorem, a characterization of NP in terms of proofs that can be checked by reading a few random bits. It yields results such as:
| Problem | Easy approximation | Limit if P ≠ NP |
|---|---|---|
| MAX-3SAT | Random assignment: 7/8 of clauses on average | Cannot beat 7/8 + ε |
| Set cover | Greedy: factor about ln n | Cannot beat (1 − ε) ln n |
| Maximum clique | Trivial: factor n | Cannot beat n^(1−ε) |
| Vertex cover | Matching: factor 2 | Constant bounds exist, but the exact value is open |
The MAX-3SAT case is remarkable: an algorithm that does no thinking at all, assigning values at random, already reaches the best possible bound.
In short
- An approximation algorithm runs in polynomial time and guarantees a bounded distance from the optimum on every instance.
- The typical technique compares the solution with an easily computed lower bound on the optimum.
- Vertex cover has a 2-approximation; the metric travelling salesman reaches 3/2 with Christofides.
- Without the triangle inequality the travelling salesman cannot be approximated within any constant, if P ≠ NP.
- The PCP theorem provides inapproximability limits, such as 7/8 for MAX-3SAT.
