a fully polynomial-time approximation scheme (FPTAS)
A PTAS lets you dial accuracy, but its running time can explode as you ask for more — something like n^(1/epsilon), useless once epsilon is small. A fully polynomial-time approximation scheme is the gold standard that removes this catch: it is a (1 + epsilon)-approximation scheme whose running time is polynomial in BOTH the input size n AND in 1/epsilon. Tighten the accuracy and the cost grows only gracefully, like a polynomial in 1/epsilon, not an explosion.
The precise requirement is the single word 'fully'. A PTAS is polynomial in n for each fixed epsilon, with no limit on how badly the running time depends on epsilon. An FPTAS upgrades this: the running time must be polynomial in n and in 1/epsilon together, for example O(n^2 / epsilon) or O(n^3 / epsilon). Now halving epsilon (doubling 1/epsilon) only multiplies the running time by a constant-ish factor, so high accuracy is genuinely affordable. The textbook way to build an FPTAS is by 'rounding and scaling' a dynamic program: take an exact DP whose running time depends on the magnitude of the numbers in the input (a pseudo-polynomial algorithm), then deliberately round those numbers down to fewer significant digits — coarse enough to make the DP fast, fine enough that the lost precision costs at most an epsilon fraction of the optimum. The chosen scaling ties the digit-coarseness directly to epsilon.
Why FPTAS sits at the top of the hierarchy: it is essentially the best you can hope for short of a polynomial exact algorithm — arbitrary accuracy at a gentle, polynomial price in both n and 1/epsilon. Knapsack and subset-sum are the celebrated examples. The honest boundaries: not every problem admits one. A standard result says that a strongly NP-hard problem cannot have an FPTAS unless P = NP, which is why FPTASes appear for number-based problems like knapsack (whose hardness comes from large numbers) but NOT for problems like general TSP or max-clique (which are hard even with tiny numbers). So an FPTAS is a wonderful outcome when it exists, but its existence is itself a strong, problem-specific fact.
The knapsack FPTAS runs in time O(n^2 / epsilon) (or similar): both n and 1/epsilon appear only polynomially. Asking for 1% accuracy (epsilon = 0.01) costs 1/epsilon = 100 as a factor — a constant multiplier, not an exploding exponent. Contrast a PTAS at n^(1/epsilon) = n^100 for the same accuracy.
Polynomial in n AND in 1/epsilon: tightening accuracy stays cheap. The strongest scheme there is.
A strongly NP-hard problem has no FPTAS unless P = NP. So FPTASes exist for number problems like knapsack (hard only because of large numbers) but not for problems like general TSP or clique that stay hard even with tiny numbers. Existence is a strong, problem-specific fact.