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 , satisfies

If an FPTAS exists, choose

Then , so the FPTAS still runs in polynomial time whenever is polynomially bounded by the input length. For a returned solution , the approximation guarantee gives

Since , the subtracted term is strictly smaller than . Hence

But and are integers, and a feasible solution cannot exceed the optimum. Therefore

So the approximation algorithm returns an exact optimum in polynomial time. For an NP-hard problem such as Bi Knapsack, this would imply .

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