Consider the classic Knapsack optimization problem (KP):

Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ and $\sum_{i\in I}p_i$ is maximum.

The textbook proof of NP-hardness reduces from the subset-sum problem and results in special KP instances that have $w_i=p_i$.

Question: Are there other (i.e., not containing the above) NP-hard instance classes of the KP known? Especially instances where more than one $\frac{p_i}{w_i}$ ratio can be present?

  • 2
    $\begingroup$ You can add arbitrary $\frac{p_i}{w_i}$ ratios by multiplying each $w_i$ by 2, setting $B = 2B+1$ and adding a new item with $w_i = 1$ and arbitrary $p_i$. The new item is always selected in the resulting instance. $\endgroup$ – Laakeri Jan 19 at 10:08
  • $\begingroup$ That’s a very nice idea. Alas, it would be nice to have instances that are structurally different. Because these new items can be easily preprocessed and we end up with the textbook instances again. $\endgroup$ – FiB Jan 19 at 12:44
  • 2
    $\begingroup$ Well, if the definition of "preprocessing" is a polynomial time reduction, then every knapsack instance can be preprocessed to obtain a textbook instance because of NP-completeness. $\endgroup$ – Laakeri Jan 19 at 13:30

Your Answer

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

Browse other questions tagged or ask your own question.