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


  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.

  • $\begingroup$ We have MathJax over here. $\endgroup$ – Yuval Filmus Feb 10 '19 at 11:32
  • $\begingroup$ You were using $S$ to denote two different things. $\endgroup$ – Yuval Filmus Feb 10 '19 at 11:32
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 10 '19 at 11:36
  • $\begingroup$ 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. $\endgroup$ – Bb23 Feb 10 '19 at 11:40
  • $\begingroup$ Your algorithm doesn't find a feasible solution. Do you have a link to the original exercise? $\endgroup$ – Yuval Filmus Feb 10 '19 at 11:42

Your Answer

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

Browse other questions tagged or ask your own question.