3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.