From a fixed ratio to a dial
The four guides before this one gave you algorithms with a single, take-it-or-leave-it approximation ratio: 2 for the vertex-cover greedy and for LP rounding, ln n for set cover, 1.5 for Christofides. Each is a fixed promise — you get exactly that quality and no choice in the matter. This last guide is about a strictly more generous situation. For some problems there is not one algorithm but a whole family, indexed by a precision knob, that lets you ask for any accuracy you like and delivers it in polynomial time. That family is an approximation scheme.
The knob is always written epsilon (a small positive number), and the contract is the same for every scheme: feed it your instance and your chosen epsilon, and it returns a solution within a factor (1 + epsilon) of the optimum. Set epsilon = 0.1 and you are guaranteed within 10%; set epsilon = 0.01 and you are within 1%. As epsilon goes to zero the answer approaches optimal. This is qualitatively better than a fixed factor 2: it says the problem has no fundamental approximation barrier at all — you can get as close to the true optimum as you are willing to pay for.
PTAS: polynomial in n, but read the small print
The weaker of the two schemes is a polynomial-time approximation scheme, or PTAS. Its promise: for each fixed epsilon, the running time is polynomial in the input size n. That word fixed is doing enormous work, and it is exactly where beginners get burned. A PTAS does not promise that the running time is polynomial in n and epsilon together — only that, once you nail epsilon to a particular value, the dependence on n is a polynomial. The dependence on epsilon itself is completely unrestricted, and in practice it is usually dreadful.
How bad can it get? A typical PTAS runs in time like O(n^(1/epsilon)) — the accuracy knob sits in the exponent. Watch what that does. At epsilon = 1/2 the cost is O(n^2), perfectly fine. At epsilon = 1/10 (within 10%) it is O(n^10), already a heavy lift. At epsilon = 1/100 (within 1%) it is O(n^100), which is polynomial on paper and utterly hopeless in reality. So a PTAS honestly is a polynomial-time algorithm for each accuracy — yet for the high accuracy you usually want, the polynomial is so steep that the word 'polynomial' tells you almost nothing useful. This is the recurring asymptotics lesson sharpened: the form 'polynomial in n' hides an exponent that can itself explode with another parameter.
Where do PTASes come from? Almost always from structure you can exploit at a tunable grain. A common pattern: chop the instance into pieces whose size is controlled by epsilon, solve each small piece near-optimally by brute force or dynamic programming, and stitch the pieces together while proving the seams cost at most an epsilon fraction of the optimum. Smaller epsilon means finer pieces, which means each piece is larger, which is exactly why the running time swells. Many problems on geometric inputs (points in the plane) and certain scheduling problems admit a PTAS by this divide-into-epsilon-sized-chunks idea.
FPTAS: the dial that stays cheap
The flaw in a PTAS is that 1/epsilon can sit in the exponent. The fully polynomial-time approximation scheme, or FPTAS, removes exactly that flaw. The single word fully means: the running time is polynomial in n AND in 1/epsilon together — for example O(n^2 / epsilon) or O(n^3 / epsilon). Now 1/epsilon is just an ordinary factor, not an exponent. Halving epsilon (doubling 1/epsilon) merely doubles a factor of the running time. High accuracy is genuinely affordable, so an FPTAS is the strongest thing you can have short of a polynomial algorithm that solves the problem exactly.
Compare the two schemes on one concrete demand — solve within 1%, so epsilon = 0.01. A PTAS at O(n^(1/epsilon)) becomes O(n^100): dead on arrival. An FPTAS at O(n^2 / epsilon) becomes O(n^2 * 100) = O(100 n^2): a constant multiplier on a quadratic algorithm, entirely practical. Same accuracy request, two wildly different worlds. The whole point of the 'fully' refinement is to move 1/epsilon out of the exponent and into a polynomial factor, and that single move is the difference between a theorist's curiosity and a tool you would actually run.
Building one: rounding and scaling for knapsack
The cleanest FPTAS in all of algorithms is the one for 0/1 knapsack — items each with a weight and a value, a sack of fixed capacity, maximize the value of a subset that fits. It is NP-hard, yet you can get within (1 + epsilon) of the best value in time polynomial in both n and 1/epsilon. The construction, called rounding and scaling, starts from the exact knapsack DP you met earlier in the ladder, and the hinge is a subtle choice within it. Knapsack's DP can be filled two ways: indexed by weight, or indexed by value. The value-indexed DP computes, for each achievable total value, the minimum weight needed to reach it; its running time is polynomial in n and in the largest item value V. If values were small this would already be fast — but V can be astronomically large, so this version is only pseudo-polynomial (polynomial in the numeric magnitude of the input, not its bit-length). The whole NP-hardness of knapsack lives in those big numbers, and rounding-and-scaling deliberately shrinks them until the value-indexed DP is fast, while losing almost nothing.
- Pick a scaling factor K = (epsilon * V_max) / n, where V_max is the largest single item value. K is small when epsilon is small, large when you tolerate more error — the knob ties directly to K.
- Replace each item's value v_i by the rounded-down scaled value floor(v_i / K). The largest scaled value is now about n / epsilon — small integers, governed by epsilon, not by the original huge V.
- Run the exact value-indexed DP on these rounded values. Because the values are now small, its running time is polynomial in n and 1/epsilon — that is the 'fully' in FPTAS, earned.
- Output the subset the DP chose, but report its TRUE (unrounded) total value. Crucially, weights were never touched, so the subset really fits the sack.
Why is the answer within (1 + epsilon)? Rounding each value down by floor(v_i / K) discards less than K of value per item. The optimal subset holds at most n items, so across the whole solution you lose less than n * K = n * (epsilon * V_max) / n = epsilon * V_max of value. And the true optimum is at least V_max, since the single most valuable item fits on its own. So the value you give up is at most an epsilon fraction of the optimum: the subset you return has true value at least (1 - epsilon) * OPT. The rounding error is bounded against OPT itself — the same surrogate-for-OPT discipline that runs through this entire rung.
When no scheme can exist
Honesty demands the other side of the ledger: most NP-hard problems do NOT have an FPTAS, and many have no PTAS either. The boundary is sharp and worth memorizing. A problem that is strongly NP-hard — meaning it stays NP-hard even when all the numbers in the input are small (bounded by a polynomial in n) — cannot have an FPTAS unless P = NP. The reasoning is clean: an FPTAS plus small numbers would let you set epsilon fine enough to pin down the exact integer optimum in polynomial time, solving a strongly NP-hard problem outright. So the whole rounding-and-scaling trick depends on the hardness living in large numbers, the way it does for knapsack and subset-sum.
This explains the pattern you should expect. Knapsack and subset-sum have FPTASes because they are hard only on account of big numbers — shrink the numbers and the hardness shrinks too. But general (non-metric) TSP and max-clique are hard even with tiny inputs, so no amount of scaling helps; in fact general TSP has no constant-factor approximation at all, let alone a scheme. Inapproximability results make these walls precise: via gap-producing reductions (ultimately powered by the PCP theorem), one proves statements like 'set cover cannot be approximated better than (1 - o(1)) ln n unless P = NP.' That is why set cover is stuck at log n and will never have a PTAS — the barrier is a theorem, not a failure of imagination.
Keep the usual caveats in view, because they govern how to read all of this. Every one of these results is worst-case and conditional: 'no FPTAS unless P = NP' rests on the open P versus NP question, and 'hard to approximate' forbids a good ratio on the worst input, not good behavior on the instances you actually face. A problem with no PTAS in theory may still be tamed in practice by fixed-parameter algorithms when a key parameter is small, or by local search and metaheuristics that carry no guarantee but often work. The scheme hierarchy tells you what is provably possible; it does not forbid clever engineering when the guarantees run out.
The whole rung in one breath
Step back and the five guides form a single arc. When a problem is NP-hard you stop demanding the optimum and ask instead for a provable, polynomial-time approximation — and the ratio is the contract. Sometimes a simple combinatorial idea suffices: take both endpoints of a maximal matching for vertex cover, grab the largest uncovered set greedily for set cover, double an MST for metric TSP. Sometimes you reach for the general machinery of LP relaxation and rounding, which mechanizes the surrogate-for-OPT bound for almost any 0/1 problem. And sometimes the problem is friendly enough to hand you a knob — a PTAS, or the gold-standard FPTAS.
Underneath every one of these sits the same intellectual move you have now seen a dozen times: you never compute OPT — it is the hard thing you are dodging — so you bound your answer against a cheap, computable stand-in for OPT (a matching, an MST, an LP value, a rounded DP). The art of approximation is the art of finding the right surrogate and proving your algorithm stays close to it. Master that move, and 'the problem is NP-hard' stops being a dead end and becomes the start of an interesting question: how close can I get, how fast, and is there a wall — and if so, where exactly does it stand?