Analysing Approximation Ratios

The previous page built approximation algorithms with fixed ratios — 2 for Vertex Cover, 3/2 for metric TSP. But fixed is not the summit of the art. For some problems you can dial the ratio as close to 1 as you are willing to pay for: hand the algorithm an \varepsilon and it returns an answer within a factor (1+\varepsilon) of optimal. That's an approximation scheme, and the whole question becomes: how does the running time blow up as \varepsilon \to 0?

The answer to that question is what separates a PTAS from an FPTAS — the two most important letters in approximation theory — and it sorts NP-hard problems into a hierarchy of "how nicely can this be approximated?" This page is about proving ratios rigorously and naming the classes those proofs land you in.

Proving a ratio, formally

Recall the discipline: you can never see \text{OPT}, so you sandwich it. For a minimisation problem, produce a computable lower bound L \le \text{OPT} and bound your output above by \rho\,L. Then

\text{ALG} \;\le\; \rho\,L \;\le\; \rho\,\text{OPT}.

The entire creative act is choosing L — a matching, an LP relaxation, a spanning tree, a fractional optimum. A cleaner and often stronger route is LP relaxation and rounding: write the problem as an integer program, relax the integrality to get a solvable linear program whose optimum \text{OPT}_{\text{LP}} \le \text{OPT} is a lower bound, solve it, then round the fractional solution to an integral one while controlling how much you lose. The ratio you can prove is exactly the integrality gap — the worst-case ratio between the integer optimum and the LP optimum.

PTAS and FPTAS

An approximation scheme takes both the instance and a target error \varepsilon > 0, and returns a (1+\varepsilon)-approximation (for minimisation). The classes are defined by how the running time depends on \varepsilon:

PTAS (Polynomial-Time Approximation Scheme): for every fixed \varepsilon, runs in time polynomial in n — but the exponent may depend on \varepsilon, so a running time like n^{1/\varepsilon} or 2^{1/\varepsilon}\,n is allowed. Halve \varepsilon and the cost can explode.
FPTAS (Fully Polynomial-Time Approximation Scheme): runs in time polynomial in both n and 1/\varepsilon — e.g. O(n^3/\varepsilon). The "fully" means 1/\varepsilon also enters only polynomially. This is the gold standard: accuracy is cheap.

Every FPTAS is a PTAS, but not conversely. The gap between them is enormous in practice, and the chart shows why: as you demand more accuracy (larger 1/\varepsilon), an FPTAS's cost creeps up linearly while a typical PTAS's cost detonates.

For a PTAS with running time 2^{1/\varepsilon}n, going from 10% error to 1% error multiplies the exponent's driver from 10 to 100 — utterly impractical. An FPTAS at n^3/\varepsilon merely gets 10× slower. When a problem has an FPTAS, take it.

The knapsack FPTAS: scale, round, then DP

The 0/1 knapsack problem — pick items of given weights and profits to maximise profit under a weight budget — is NP-hard, yet it has a beautiful FPTAS. The key is a dynamic-programming solution whose running time depends on the profit values, not just the item count: O(n \cdot P) where P is the largest profit. That is fast only when profits are small — so we make them small by rounding.

Let p_{\max} be the largest item profit. Choose a scaling factor K = \dfrac{\varepsilon\, p_{\max}}{n}.
Round every profit down: p_i' = \left\lfloor p_i / K \right\rfloor. The rounded profits are small integers.
Solve knapsack exactly on the rounded profits by the O(n^2 p_{\max}/K) = O(n^3/\varepsilon) DP.

Rounding each of at most n chosen items loses less than K profit apiece, so the total loss is under nK = \varepsilon\,p_{\max} \le \varepsilon\,\text{OPT} (since \text{OPT} \ge p_{\max}). Hence \text{ALG} \ge (1-\varepsilon)\,\text{OPT} — a (1+O(\varepsilon))-approximation in time polynomial in n and 1/\varepsilon. An FPTAS.

The whole trick in one sentence: the DP is slow because the numbers are big, so throw away the low-order bits of the numbers — as many as the error budget allows — and the same DP becomes fast, at a controlled cost in accuracy.

The class APX

Just as P and NP classify decision problems, optimisation problems get their own zoo, nested by how well they approximate:

Class	Best achievable	Example
FPTAS	(1+\varepsilon), cost poly in n, 1/\varepsilon	Knapsack
PTAS	(1+\varepsilon), cost poly in n for fixed \varepsilon	Euclidean TSP, bin packing
APX	Some fixed constant ratio \rho	Vertex Cover, metric TSP, MAX-3SAT
(beyond APX)	No constant ratio (e.g. \Theta(\ln n))	Set Cover, Max Clique

APX is the class of problems with some constant-factor polynomial-time approximation. The inclusions \text{FPTAS} \subseteq \text{PTAS} \subseteq \text{APX} are strict (assuming \text{P} \neq \text{NP}): there are APX problems with no PTAS at all. A problem being APX-hard means it has no PTAS unless \text{P}=\text{NP} — the frontier the PCP theorem lets us prove.

Knapsack is only weakly NP-hard — hard when the numbers are written in binary and can be astronomically large, but solvable in O(nP) pseudopolynomial time that is polynomial in the numeric value P. That is precisely the hook an FPTAS needs: scale the values down so the pseudopolynomial DP becomes genuinely fast, paying a controlled accuracy cost. A deep theorem makes this general — a problem with a "nice" objective has an FPTAS essentially iff it has a pseudopolynomial algorithm. Strongly NP-hard problems (hard even with small numbers, like TSP) have no FPTAS unless \text{P}=\text{NP}, no matter how clever you are.

"This problem has a PTAS" sounds like a happy ending, but read the running time before you celebrate. A PTAS is polynomial in n for each fixed \varepsilon — yet the exponent, or a leading constant, may depend on \varepsilon so violently that even \varepsilon = 0.1 is unrunnable. Some celebrated PTASes have constants like 2^{2^{1/\varepsilon}} or exponents in the thousands — technically polynomial, practically fiction. The lesson: "has a PTAS" is a theoretical classification. An FPTAS, with its honest 1/\varepsilon dependence, is the property you actually want to run.