Give up optimality, keep polynomial time, and demand a proof of how far off you can possibly be.
The last chapter, and the constructive answer to the previous one. If a problem is NP-hard, an exact polynomial algorithm is out of reach — but a near-optimal one may not be. An approximation algorithm runs in polynomial time and comes with a theorem bounding how bad its output can be relative to the true optimum. What distinguishes it from a heuristic is exactly that theorem: a heuristic usually works, an approximation algorithm provably never fails by more than a stated factor.
ρ(n) if, for any input of size n, the cost C of its solution and the optimal cost C* satisfymax( C/C* , C*/C ) ≤ ρ(n)The two-sided form covers both minimisation (where C ≥ C*) and maximisation (where C ≤ C*) with one definition. By convention ρ(n) ≥ 1, and ρ = 1 means exact. Such an algorithm is called a ρ(n)-approximation algorithm.
C*, which you cannot compute — that is why you are approximating. Every proof in this chapter therefore works by finding a computable lower bound on C* (for minimisation) and comparing the algorithm’s output against that instead. Learning to spot the right bound is the skill the chapter teaches.A vertex cover is a set of vertices touching every edge. Finding a minimum one is NP-hard. The approximation algorithm is startlingly simple, and the first thing everybody tries — greedily picking the highest-degree vertex — is not it, and has no constant ratio.
APPROX-VERTEX-COVER(G)
1 C = ∅
2 E′ = G.E
3 while E′ ≠ ∅
4 let (u,v) be an arbitrary edge of E′
5 C = C ∪ {u, v} // take BOTH endpoints
6 remove from E′ every edge incident on u or v
7 return CO(V + E). Pick any uncovered edge, take both of its endpoints, repeat.
C* ≥ |M|. The algorithm returns exactly 2|M| vertices. Hence C = 2|M| ≤ 2C*.Find a minimum-weight cycle visiting every vertex once. Two cases, and they could not differ more.
If the weights satisfy w(u,w) ≤ w(u,v) + w(v,w) — true of any geometric or metric instance — there is a clean 2-approximation.
APPROX-TSP-TOUR(G, w)
1 select a vertex r ∈ G.V to be a root
2 compute a minimum spanning tree T for G from root r // Chapter 21
3 let H be the list of vertices in a preorder walk of T // Chapter 20
4 return the Hamiltonian cycle Hw(T) ≤ C* — the MST is the lower bound. (2) A full walk of T traverses every edge twice, costing 2w(T). (3) The preorder walk shortcuts repeated vertices, and by the triangle inequality shortcutting never increases the cost. So C ≤ 2w(T) ≤ 2C*.P ≠ NP, then for any constant ρ ≥ 1 there is no polynomial-time ρ-approximation algorithm for general TSP.The proof is a lovely piece of reasoning by contradiction. Given a Hamiltonian-cycle instance G, build a complete graph where edges of G get weight 1 and non-edges get weight ρ|V| + 1. If G has a Hamiltonian cycle, the optimal tour costs |V|; if not, every tour must use at least one huge edge and costs more than ρ|V|. A ρ-approximation could distinguish these two cases and would therefore solve Hamiltonian cycle in polynomial time.
Given a universe X and a family F of subsets covering it, find the fewest subsets whose union is X. This generalises vertex cover and models resource selection, facility location, and test-suite minimisation.
GREEDY-SET-COVER(X, F)
1 U = X; C = ∅
2 while U ≠ ∅
3 select S ∈ F that maximises |S ∩ U| // most new elements
4 U = U - S
5 C = C ∪ {S}
6 return CH(max{|S|})-approximation, where H(d) = 1 + 1/2 + … + 1/d is the dth harmonic number. So the ratio is O(lg n) — not constant, but logarithmic.ln n is the best possible. It was later proved that no polynomial-time algorithm achieves (1 - ε) ln n for set cover unless P = NP. So the obvious greedy algorithm is, up to lower-order terms, optimal. That happens more often than intuition suggests, and it is a good argument for trying greedy first and then trying to prove it tight.The chapter’s most surprising result, and the shortest.
MAX-3-CNF satisfiability: given a 3-CNF formula, satisfy as many clauses as possible. NP-hard. The algorithm:
Set each variable to TRUE or FALSE independently at random,
each with probability 1/2.(1/2)³ = 1/8. So each clause is satisfied with probability 7/8. By linearity of expectation (Chapter 5), the expected number satisfied is 7m/8. Since the optimum is at most m, the expected ratio is at most 8/7.And this is essentially tight: approximating MAX-3-CNF better than 8/7 is NP-hard, so random guessing is optimal up to a vanishing margin.
The most broadly useful technique, and the reason Chapter 29 appears in this book.
1. Formulate the problem as an integer linear program. (NP-hard)
2. Relax it: allow variables to take fractional values. (solvable)
3. Solve the LP in polynomial time.
4. Round the fractional solution to an integer one.
5. Prove the rounding costs at most a bounded factor.For weighted vertex cover, the ILP has xᵛ ∈ {0,1} for each vertex and a constraint xᵘ + xᵛ ≥ 1 for each edge. Relax to 0 ≤ xᵛ ≤ 1, solve, then round:
include vertex v in the cover ⇔ xᵛ ≥ 1/2xᵘ + xᵛ ≥ 1 forces at least one endpoint to be ≥ 1/2, so every edge is covered. Quality: rounding at most doubles each included variable, so the cost at most doubles. And the LP optimum is a lower bound on the ILP optimum, since the LP optimises over a superset of the feasible region — there is the computable bound again.The gap between the LP optimum and the ILP optimum is the integrality gap, and it caps how good any rounding-based approximation can be.
Sometimes you can get arbitrarily close, if you are willing to pay for it.
| Scheme | Running time | Meaning |
|---|---|---|
| PTAS polynomial-time approximation scheme | Polynomial in n for each fixed ε, but may be exponential in 1/ε — e.g. O(n2/ε) | Any accuracy, at a price that explodes as ε → 0 |
| FPTAS fully polynomial-time approximation scheme | Polynomial in both n and 1/ε — e.g. O(n³/ε) | The best you can hope for on an NP-hard problem |
CLRS gives an FPTAS for subset sum. The exact algorithm enumerates all achievable subset sums, which grow exponentially. The approximation trims the list after each step, discarding any value within a factor 1 + ε/2n of one already kept. That keeps the list polynomially short while bounding the accumulated error, giving a (1 + ε)-approximation in time polynomial in n and 1/ε.
| Problem | Best known ratio | Hardness of approximation |
|---|---|---|
| Subset sum, knapsack | FPTAS — any 1 + ε | None |
| Euclidean TSP | PTAS | None known |
| Metric TSP | 3/2 (Christofides) | No better than 123/122 |
| Vertex cover | 2 | No better than 1.36; 2 is conjectured tight |
| MAX-3-CNF | 8/7 — by coin flips | 8/7 is tight |
| Set cover | ln n | ln n is tight |
| Maximum clique | n1-ε | Essentially inapproximable |
| General TSP | None | No constant ratio possible |
ρ-approximation algorithm runs in polynomial time and is provably within a factor ρ of optimal. The proof is what separates it from a heuristic.w(MST) ≤ C* and the triangle inequality to justify shortcutting. Christofides gets 3/2.P = NP. The triangle inequality is load-bearing.O(lg n)-approximation, and ln n is provably the best possible.n and 1/ε) is the best outcome available; subset sum has one, via trimming.Thirty-five chapters, and the arc closes where it began. Chapter 1 claimed that efficiency is a resource you buy with thought rather than hardware, and that some problems resist every amount of thought. Part I built the tools to say what efficiency means; Parts II to VI spent them on sorting, structures, and graphs; Chapter 34 identified where the tools stop working; and Chapter 35 showed what to do at that boundary — not surrender, but a smaller, provable promise. Knowing exactly how good your answer is remains a form of correctness.