0
$\begingroup$

In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack.

I want to add a conditional constraint: $V = {V_1, V_2, ..., V_d}$, where each $i$-th dimension in the knapsack must have a value sum greater than threshold $V_i$. I am not so much concerned with the total value sum.

I would like to show this problem is NP-hard. My intuition is that the additional constraint makes this problem harder than MKD and therefore is NP-hard. But clearly this doesn't constitute a formal proof.

$\endgroup$

1 Answer 1

0
$\begingroup$

Your intuition is right on. If I understand correctly, when $V_1=\cdots=V_d=0$, then your problem becomes exactly the ordinary knapsack problem. So, the knapsack problem is a special case of your problem. That means that your problem is at least as hard as the knapsack problem, i.e., your problem is NP-hard.

You can prove this formally by exhibiting a reduction that converts a knapsack problem to an instance of your problem by setting $V_1=\cdots=V_d=0$; thus any algorithm that can solve your problem can be used to solve the knapsack problem, too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.