# Non-existence of approximation algorithm for the knapsack problem

I am working on the following exercise: Prove that if $$P \neq NP$$, there cannot exist an approximation algorithm $$A$$ for the knapsack problem (KP) such that $$\exists k \in \mathbb{N}, \forall I \in S: OPT(I) – P_A(I) \leq k$$ where $$OPT(I)$$ is the optimal profit on instance $$I$$ and $$P_A(I)$$ is the profit calculated by $$A$$.

I know that there is a FPTAS $$A’$$ for the KP which guarantees a solution with profit $$P_{A’}(I) \geq (1 – \varepsilon)OPT(I)$$ on any instance $$I$$ and $$\varepsilon > 0$$.

My approach is to create a contradiction. For this I consider $$A = A’$$ and aim to show that $$P_A(I) \geq (1 – \varepsilon)OPT(I) \geq … \geq OPT(I) – c$$ where $$c \in (0,1)$$ is a constant. This way, for an adequate choice of $$\varepsilon$$ I would show that we obtain an optimal solution within polynomial time. However, I struggle how to choose $$\varepsilon$$.

I need some advice on how to proceed. Many thanks in advance!

Posted on Categories proxies