2
$\begingroup$

Is 0-1 knapsack problem still NP-Hard with an equality constraint?

$$\begin{aligned} & \text { maximize } \sum_{i=1}^n v_i x_i \\ & \text { subject to } \sum_{i=1}^n w_i x_i = W \text { and } x_i \in\{0,1\} \text {. } \end{aligned}$$

What if $w_i=1$ for all $i = \{1,\dots,n\}$? Is 0-1 knapsack problem still NP-Hard when all the weights in the constraint are equal to one?

$$\begin{aligned} & \text { maximize } \sum_{i=1}^n v_i x_i \\ & \text { subject to } \sum_{i=1}^n x_i = W \text { and } x_i \in\{0,1\} \text {. } \end{aligned}$$

$\endgroup$
6
  • $\begingroup$ If you solve the LP relaxation with the simplex algorithm you will get a binary solution. So clearly the problem is not NP hard. $\endgroup$ Commented Jun 17 at 6:20
  • $\begingroup$ I believe it is still NP-hard with the equality constraints. link $\endgroup$
    – Anson
    Commented Jun 17 at 6:48
  • $\begingroup$ I assumed w_i=1 and W is positive integer. Any feasible basic solution must be an integer feasible solution IMO. $\endgroup$ Commented Jun 17 at 6:57
  • $\begingroup$ Please ask only one question per post. It appears you added an entirely different question at the end in revision 3. Can you say more about the reasons for that revision? $\endgroup$
    – D.W.
    Commented Jun 17 at 7:52
  • $\begingroup$ I was thinking about using the knapsack problem to prove the NP-hardness of the problem I have. The constraint $|S_t| \leq K$ can be seen as an inequality constraint with all weights that are equal to one. $\endgroup$
    – Anson
    Commented Jun 17 at 8:09

1 Answer 1

7
$\begingroup$

The general case where not all weights are equal to one, is ${NP}$ hard, as the subset sum problem reduces to it with a constant objective function.

If all weights $w_i$ are equal to one, the problem can be solved in ${O}(n\log (n))$ time, as you can solve the problem $\max\{v^Tx:\mathbf{1}^Tx=W, x\in\{0,1\}^n\}$ by sorting the items in non-increasing order of $v_i$ and then set $x_i=1$ for the first $W$ items, and $x_i=0$ for the remaining $n-W$ items.

$\endgroup$
3
  • $\begingroup$ Thank you! This is very informative. I have two related questions. (1) Is the problem still NP-hard if all weights $w_i$ are equal to one but with an inequality constraint? (I think it is still NP-hard as the subset sum problem reduces to it.) (2) I have a problem that I know the time complexity in the worst case to solve is in exponential time but I had a hard time coming up with a NP-hard proof for it. Do you have any suggestions? (Just updated the problem in this post). $\endgroup$
    – Anson
    Commented Jun 17 at 6:42
  • 1
    $\begingroup$ To answer (1): You solve the inequality variant, $\max\{v^Tx:\mathbf{1}^Tx \leq W, x\in\{0,1\}^n\}$, much the same way. Among the W first items, you just only choose the subset of items with positve value, $v_i > 0$, as they are the ones that increase the objective value. $\endgroup$ Commented Jun 17 at 7:11
  • $\begingroup$ Got it! Thanks. $\endgroup$
    – Anson
    Commented Jun 17 at 7:20

Your Answer

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

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