Timeline for Knapsack problem with value range constraint
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2021 at 14:48 | comment | added | Rise of Kingdom | Thank you very much! You are a very nice person and I wish I could learn more from you. | |
| Apr 22, 2021 at 14:47 | comment | added | Max Alekseyev | @EricHuang: Thanks, but that's just an experience. The more examples and techniques you know, the better vision you have for what can be done with a particular problem. | |
| Apr 22, 2021 at 14:43 | comment | added | Rise of Kingdom | Btw, I am very impressed by your reduction skill. How could you think of such nice reduction? Could you share some tips on doing reduction? | |
| Apr 22, 2021 at 14:43 | comment | added | Max Alekseyev | @EricHuang: If you mean my answer, then correspondence is direct -- any solution $(p_h)$ to the new problem represents a solution to the old one as well. | |
| Apr 22, 2021 at 14:41 | comment | added | Rise of Kingdom | I got your point about the "super useful" item. But I am still a little bit confused about the correspondence establishment about multiplying $c$. | |
| Apr 22, 2021 at 14:40 | comment | added | Max Alekseyev | @EricHuang: Since we can accommodate this super useful item ($B^*:=B+w_*>w_*$), the optimal solution must include it. | |
| Apr 22, 2021 at 14:38 | comment | added | Max Alekseyev | @EricHuang: You show this by establishing correspondence between solutions to a new problem and solutions to the old one. | |
| Apr 22, 2021 at 14:36 | comment | added | Rise of Kingdom | Btw, I know it is intuitive that multiplying all $w_h$ and $B$ by a parameter $c$ will not influence the solution. But it becomes tricky when you want to formalise this intuition. How can we formally show that multiplying by $c$ will result in the same solution? | |
| Apr 22, 2021 at 14:36 | comment | added | Max Alekseyev | @EricHuang: Super useful item is more useful than all other items altogether ($v_* > \sum_h v_h$), and so it must be present in the solution. | |
| Apr 22, 2021 at 14:33 | comment | added | Rise of Kingdom | Hi Max, based on my understanding of your reduction. When $\sum_{h} (w_h+v_h)/2<B$, we will never choose the useless item, and the solution of the new problem is the solution of my original problem. When $\sum_{h} (w_h+v_h)/2>B$, we will always choose the ``super useful" item and the solution of the new problem is the solution of my original problem plus the "super useful" item. But how we can make sure that the "super useful" item will be always chosen in the new problem? Otherwise, the introduced extra weight $w_*$ will impact the solution of my original problem. | |
| Apr 22, 2021 at 13:28 | comment | added | Max Alekseyev | @EricHuang: Yes, it's also NP-hard. To reduce your original problem to this new one, we can consider two cases. If $\sum_h (w_h+v_h)/2 < B$, we add a new "useless" item with $v_* := 0$ and $w_* := 2B - \sum_h (w_h+v_h)$. If $\sum_h (w_h+v_h)/2 > B$, we add a new "super useful" item with $v_* := 1 + \sum_h v_h$ and increase $B$ by its capacity $w_* := v_* + \sum_h (w_h+v_h) - 2B > v_*$, implying that $(w_* + v_*)/2 + \sum_h (w_h+v_h)/2 = B + w_*$. | |
| Apr 21, 2021 at 10:36 | comment | added | Rise of Kingdom | Hi Max, I have a follow up question. If I have one more constraint on $B$ which is $\sum_{h=1}^i (w_h+v_h)/2 =B$, is this problem still NP-hard? | |
| Apr 21, 2021 at 10:33 | vote | accept | Rise of Kingdom | ||
| Apr 20, 2021 at 6:07 | vote | accept | Rise of Kingdom | ||
| Apr 21, 2021 at 10:33 | |||||
| Apr 19, 2021 at 10:25 | comment | added | Max Alekseyev | Vice versa, generic knapsack is reduced to your problem by multiplying its parameters by suitable $c$. This proves NP-hardness of your problem. | |
| Apr 19, 2021 at 9:07 | comment | added | Rise of Kingdom | So is my problem just a special case of the generic knapsack problem you formulated with c=1? If so, it may not be sufficient to prove the NP-hardness of my knapsack problem. Is it correct? | |
| Apr 15, 2021 at 12:04 | history | answered | Max Alekseyev | CC BY-SA 4.0 |