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?


$$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.

  • $\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 Oct 2 '18 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$ – Arthur M Oct 2 '18 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 Oct 2 '18 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$ – Arthur M Oct 2 '18 at 22:40
  • $\begingroup$ If QKP is NP-hard then so is your problem - just don’t use any cardinality constraints. $\endgroup$ – Yuval Filmus Oct 2 '18 at 22:55

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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