1
$\begingroup$

Suppose we have a sequence of containers each of which contains multiple items. Each item $I_i$ is associated with an nonnegative weight $w_i$, a nonnegative value $v_i$, and $I_i(C)$ denotes the ID of the container item $I_i$ belongs to. Given a bag with capacity $B$, the problem aims to select items into the bag without exceeding the capacity $B$ under the constraints that items being selected must come from different containers. Formally, the goal is

$$\text{maximise } \sum_h p_h*v_h $$ subject to: (1) $p_h=1$ or 0. (2) $\sum_h p_h*w_h \leq C$. (3) $\forall j,k$, if $p_j=p_k=1$, $I_j(C) \neq I_k(C)$.

I know we can reduce the traditional knapsack problem to my problem when the size of each container is 1. But this reduction does not imply that my problem is strongly NP-hard since the traditional knapsack problem is weakly NP-hard. So my question is: can we reduce a strongly NP-hard problem to my problem?

Another thing I want to share which is not really relevant though, is that my problem can be reduced to knapsack problem with conflict graphs which is known to be strongly NP-hard.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The same dynamic programming solution works for your instance as for knapsack. Just order the elements according to which container contains them. Then for each weight/value/container_of_last_added_element triple, you can compute the optimum by dynamic programming.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Your feedback is very helpful. I have a follow up question. Will the problem become strongly NP-hard if there exists conflict between containers such that items from different containers cannot be picked at the same time under some conditions? E.g., Suppose $I_i(C)(median)$ denotes the median weight of all items in the container containing item $I_i$, we have the constraint: if $p_j=p_k=1$ and $I_j(C)(median)\leq I_k(C)(median)$, $ \frac{I_j(C)(median)}{v_j} \leq \frac{I_k(C)(median)}{v_k}$. $\endgroup$ Commented May 16, 2021 at 6:52
  • $\begingroup$ In this case, not only items in the same container have conflicts but items from different containers. I do not think that the same dynamic programming can solve this problem. This new problem becomes more like the knapsack problem with conflict graphs but showing this new problem seems to be non-trivial. The knapsack problem with conflict graphs can be shown to be strongly np-hard via reduction from the maximum independent set problem. But we cannot reduce the independent problem to this new problem I configured. $\endgroup$ Commented May 16, 2021 at 7:00
  • $\begingroup$ I think that this new variant you can put an arbitrary number of dummy elements into each container with (near) zero value. If each container has just one non-dummy element, then this is like the conflict graph version in the special case when the graph is a threshold graph. I'm not sure about the complexity of this problem. BTW, let me mention that such questions are a better fit for cstheory.stackexchange.com instead of mathoverflow. $\endgroup$ Commented May 16, 2021 at 7:16
  • $\begingroup$ I thought mathoverflow is the place for research-level stuff based on people's comments on the internet. Stachexchange seems to be not well relevant to theoretical research. $\endgroup$ Commented May 16, 2021 at 7:36
  • $\begingroup$ It depends on the field. I did not recommend math.stackchange.com, but cstheory.stackexchange.com, which used to be a part of mathoverflow. $\endgroup$ Commented May 16, 2021 at 14:40

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.