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 know we usually talk about the hardness of Decision Problems even tough I'm formalizing the Optimization version of it.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.