1
$\begingroup$

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it.

Besides, it's easy to see that the KP problem is a special case of the QKP.

How should one proceed to prove the NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem?

CCQKP:

$$max\ \sum_{i=1}^{n} \sum_{j=1}^{n} x_i x_j c_{ij}$$ $s.t$ $$\sum_{j=1}^{n} a_j x_j \leq C$$ $$\sum_{j=1}^{n}x_j = 1$$ $$0 \leq x_j \leq 1,\ j = 1,...,n$$ $$\sum_{j=1}^{n}z_j = k$$ $$z_j \in \{0,1\},\ j = 1,...,n$$

I'm aware that we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.

Improve this question
$\endgroup$
5
  • $\begingroup$ Is there anything to do? The decision problem directly reduces to the optimization problem: if you want to know "Is there a widget with weight at least $w$?" you can just compute the maximum weight of any widget and answer "yes" if that is at least $w$. $\endgroup$
    – David Richerby
    Commented Oct 2, 2018 at 14:57
  • $\begingroup$ I understand that the decision problem reduces to the optimization problem. What I'm rather interested in is how I can prove the hardness of the CCQKP. I'm sorry if the question is vague. $\endgroup$
    – afm
    Commented Oct 2, 2018 at 15:53
  • $\begingroup$ When we say that an optimization problem is NP-hard, we really mean that its decision version is NP-hard. For a maximization problem, the decision version gets an instance and a value $\theta$, and the goal is to decide whether there is a feasible solution of value at least $\theta$. $\endgroup$
    – Yuval Filmus
    Commented Oct 2, 2018 at 16:26
  • $\begingroup$ @YuvalFilmus sure, I understand that. What I'm asking, though, is how I can prove that the CCQKP is NP-Hard given that both the CCKP and the QKP are NP-Hard. $\endgroup$
    – afm
    Commented Oct 2, 2018 at 22:40
  • $\begingroup$ If QKP is NP-hard then so is your problem - just don’t use any cardinality constraints. $\endgroup$
    – Yuval Filmus
    Commented Oct 2, 2018 at 22:55

1 Answer 1

Reset to default
0
$\begingroup$

The quadratic knapsack problem is NP-hard. Therefore, the cardinality-constrained quadratic knapsack problem is NP-hard, too (as Yuval says, just don't use any cardinality constraints).

If problem X is a special case of problem Y, and problem X is NP-hard, then so is problem Y. Now let X = CCQKP and Y = QKP.

Improve this answer
$\endgroup$

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.