Approximation's Collapse to Exactness

An FPTAS can collapse to an exact polynomial-time algorithm when the objective values are integral and polynomially bounded.

The mechanism is simple. Suppose a maximisation problem has integer objective values and, for every instance $I$, satisfies

$$0\le \mathrm{OPT}(I)\le n.$$

If an FPTAS exists, choose

$$\epsilon =\frac{1}{n+1}.$$

Then $1/\epsilon =n+1$, so the FPTAS still runs in polynomial time whenever $n$ is polynomially bounded by the input length. For a returned solution $B$, the approximation guarantee gives

$$|B|\ge \left(1-\frac{1}{n+1}\right)\mathrm{OPT}(I)=\mathrm{OPT}(I)-\frac{\mathrm{OPT}(I)}{n+1}.$$

Since $\mathrm{OPT}(I)\le n$, the subtracted term is strictly smaller than $1$. Hence

$$|B|>\mathrm{OPT}(I)-1.$$

But $|B|$ and $\mathrm{OPT}(I)$ are integers, and a feasible solution cannot exceed the optimum. Therefore

$$|B|=\mathrm{OPT}(I).$$

So the approximation algorithm returns an exact optimum in polynomial time. For an NP-hard problem such as Bi Knapsack, this would imply $\mathrm{P}=\mathrm{NP}$.

The insight is that a very small multiplicative error becomes no error at all when the objective scale is discrete and bounded.