0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We have MathJax over here. $\endgroup$ – Yuval Filmus Feb 10 at 11:32
  • $\begingroup$ You were using $S$ to denote two different things. $\endgroup$ – Yuval Filmus Feb 10 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 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 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 at 11:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.