Exact Optimisation via Integrality (FPTAS)

Definition

Exact Optimisation via Integrality (FPTAS)

Let be an NP-optimisation problem with integer objective function

s.t. on every instance the optimal value of satisfies

for some polynomial , where denotes the length of the unary encoding of .

If admits an FPTAS, then it also admits a pseudo-polynomial time algorithm .

Proof for Maximisation Problems

Proof for Maximisation Problems

Let be an FPTAS for , and assume

where is the length of the unary encoding of , for some polynomial . Also assume that the objective values are integers.

Choose so the approximation error is .

Set

Given that is an FPTAS,

Given the assumption , we get

Integrality makes the solution exact.

We always have that

Together with the above, i.e.,

we get the inequality chain

Both values are integers, forcing

Thus returns an optimal solution for this choice of .

Show that is pseudo-polynomial.

An FPTAS runs in

Substitute

Since binary encoding is compact, we know that

i.e., this is polynomial in . Therefore, is pseudo-polynomial.