# Knapsack approximation algorithm (weights scaling)

I am trying to prove the following Knapsack approximation algorithm, the problem definition:

Input:

1. A set $$S$$ of $$n$$ objects that contains weights and values:

• $$w_1,w_2,\ldots,w_n$$ (weights)
• $$v_1,v_2,\ldots,v_n$$ (values)
2. $$W$$ — The total weight bound.

3. Scaling factor $$0 < c < 1$$

Output: Let set $$\mathrm{OPT}(S)$$ be the optimal solution (set of items with maximum values that their total weight is less than $$W$$) of the problem, I want to find a set $$T$$ whose value $$\sum_{i \in T} v_i$$ is a least $$c \cdot \sum_{i \in \mathrm{OPT}(S)} v_i$$.

The algorithm:

1. for $$i$$ from 1 to $$n$$:
• $$w'_i = c \cdot w_i$$.
2. run the Dynamic Programing algorithm with the scaled items (table size $$n \times cW$$) — Knapsack Dynamic programming (Definition A).

I am not sure what is the exact reason why this is working. I know that because I am only scaling the weights, the values are still the same, and the ratio between the weight/value of each item is remaining almost the same (depending on $$c$$).

I am also required to prove the correctness of this approximation algorithm by proving the following lemma:

For every $$i \in T$$ there are items $$i_1,\ldots,i_k \in \mathrm{OPT}(S)$$ such that $$v_i \geq c \sum_{j=1}^k v_{i_j}$$.

The first direction of the proof is immediate if $$i \in T \cap \mathrm{OPT}(S)$$.

I got lost trying to prove the other side when $$i \notin \mathrm{OPT}(S)$$.

I would be thankful to get some explanation and guidance.

• We have MathJax over here. – Yuval Filmus Feb 10 at 11:32
• You were using $S$ to denote two different things. – Yuval Filmus Feb 10 at 11:32
• I don't really understand the point of your algorithm. Here is the scaling approach done correctly: web.cs.iastate.edu/~cs511/handout08/Approx_Knapsack.pdf. – Yuval Filmus Feb 10 at 11:36
• Yeah thanks, I already saw this one. in the algorithm, you attached the scaling is for the values. I am asked to show that the algorithm I posted that scale the weights it's working. I already search online for it. – Bb23 Feb 10 at 11:40
• Your algorithm doesn't find a feasible solution. Do you have a link to the original exercise? – Yuval Filmus Feb 10 at 11:42