<p>Consider the classic Knapsack optimization problem (KP):</p>

<p>Given <span class="math-container">$p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$</span>, compute a solution <span class="math-container">$I\subseteq \{1,\dots,n\}$</span>, such that <span class="math-container">$\sum_{i\in I} w_i \leq B$</span> and <span class="math-container">$\sum_{i\in I}p_i$</span> is maximum.</p>

<p>The textbook proof of NP-hardness reduces from the subset-sum problem and results in special KP instances that have <span class="math-container">$w_i=p_i$</span>.</p>

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

CC BY-SA 4.0
2020-01-19T10:08:44.807Z
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.
Laakeri
CC BY-SA 4.0
2020-01-19T12:44:33.533Z
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.
FiB
CC BY-SA 4.0
2020-01-19T13:30:40.363Z
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.
Laakeri
<np-hardness><optimization>
NP-Hard Knapsack Instances
FiB
# NP-Hard Knapsack Instances

(Asked by: username_0 on 2020-01-18)

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?

**Tags:** np-hardness, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 0 answers

