patternMinor
Non-existence of approximation algorithm for the knapsack problem
Viewed 0 times
problemtheapproximationexistencenonalgorithmforknapsack
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!
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!
Solution
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.
Context
StackExchange Computer Science Q#109962, answer score: 3
Revisions (0)
No revisions yet.