CODEWITHSUNDEEP
algorithmknapsack-problemapproximation
jboss
jboss

Reputation: 1

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 \mathhbb{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!

Upvotes: 0

Views: 154

Answers (1)

user58697
user58697

Reputation: 7923

The contradiction is a bit more subtle.

Consider an instance I' derived from I by increasing all the values of the items in I n-fold. An optimal profit Opt(I') is n-times the optimal profit of Opt(I), and the solution to both problems is comprised by the same set of items (prove it!).

So, if A finds the Opt(I') - k solution, it also finds an Opt(I) - k/n one. Making n large enough, conclude A would solve any instance I better than Opt(I) * (1 - eps) for any given eps.

For the integer values it is enough to take any n > k. For the real values you need some more work, namely to prove that A' is not universal, but must depend on eps.

Upvotes: 1

Related Questions