0
$\begingroup$

Suppose I have a variant of the knapsack problem:

$$\max_{x} \sum_{i=1}^n v_ix_i$$

$$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$

for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > 0$.

Is it known if the decision problem $\sum_{i=1}^n v_ix_i > V$ for some $V$ is NP-Complete?

$\endgroup$

1 Answer 1

0
$\begingroup$

The problem is clearly in $\mathsf{NP}$. You can see that it is $\mathsf{NP}$-hard by a reduction from subset sum: given a set $X = \{ x_1, \dots, x_m \}$ of positive integers and another integer $T>0$, is there a subset $S$ of $X$ such that $\sum_{x \in S} x = T$?

To reduce to your version of subset sum, create $n=m$ items, where the $i$-th item has value $v_i = 1$ and weight $w_i=2x_i$, and set $W=2T$, $k=1$, $V=0$. There is a solution to this "knapsack" instance if and only if there is a solution to the subset sum problem.

$\endgroup$
2
  • $\begingroup$ I see. Though I'm specifying $k > 0$, it sounds like you can make all $w$ and $W$'s integer and then choose $k < 1$. Seems like I need stronger conditions on $k$... $\endgroup$ May 9, 2022 at 17:38
  • $\begingroup$ I slightly modified the reduction to ensure $k>0$. $\endgroup$
    – Steven
    May 9, 2022 at 22:14

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.