Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

Question

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.

Answer 1

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.