<p>Kellerer et. al. showed in Knapsack Problems (Springer), that the Multidimensional Knapsack is W[1]-hard w.r.t. <span class="math-container">$k$</span> (the required profit), even if <span class="math-container">$d=2$</span> (dimension).</p>
<p>Albrecht et. al. (in &quot;Knapsack Problems: A Parameterized Point of View&quot;) generalized the result to <span class="math-container">$d\ge 2$</span>.</p>
<p>With either result, Multidimensional Knapsack is para-NP-hard with respect to <span class="math-container">$d$</span>. Thus, it is unlikely that Multidimensional Knapsack is in the class XP w.r.t. the dimension <span class="math-container">$d$</span>.</p>

CC BY-SA 4.0
2022-01-17T16:58:13.440Z
2022-01-17T16:58:13.440Z
xtyner
<p>Under <a href="https://cstheory.stackexchange.com/questions/21865/multidimensional-knapsack-strongly-np-complete">Multidimensional knapsack STRONGLY NP-complete</a> it was discussed that the Multidimensional Knapsack problem is strongly NP-hard.</p>

<p>Within this discussion the question whether the problem is W[1]-hard when parameterized by dimension d was mentioned, but not finally answered. Is the problem solved?</p>

<p>And: Is there any known xp-algorithm for multidimensional knapsack w.r.t. parameter dimension?</p>

CC BY-SA 3.0
2014-04-19T14:46:13.613Z
Sure the problem is at least W[1]-hard (unless P=NP). Because Knapsak is already NP-Complete.
Saeed
CC BY-SA 4.0
2022-06-24T05:11:03.800Z
Do you perhaps mean for inputs where input numbers are encoded in unary?
daniello
<parameterized-complexity>
Multidimensional Knapsack W[1]-hard when parameterized by dimension
Thomas
# Multidimensional Knapsack W[1]-hard when parameterized by dimension

(Asked by: username_0 on 2014-04-17)

Under [Multidimensional knapsack STRONGLY NP-complete](https://cstheory.stackexchange.com/questions/21865/multidimensional-knapsack-strongly-np-complete) it was discussed that the Multidimensional Knapsack problem is strongly NP-hard.

Within this discussion the question whether the problem is W[1]-hard when parameterized by dimension d was mentioned, but not finally answered. Is the problem solved?

And: Is there any known xp-algorithm for multidimensional knapsack w.r.t. parameter dimension?

**Tags:** parameterized-complexity

> **Comments:**
> **username_1**: Sure the problem is at least W[1]-hard (unless P=NP). Because Knapsak is already NP-Complete.  
> **username_2**: Do you perhaps mean for inputs where input numbers are encoded in unary?  

---

## 1 answers

### Answer by username_3 on 2022-01-17. Score: 1

Kellerer et. al. showed in Knapsack Problems (Springer), that the Multidimensional Knapsack is W[1]-hard w.r.t. $k$ (the required profit), even if $d=2$ (dimension).

Albrecht et. al. (in "Knapsack Problems: A Parameterized Point of View") generalized the result to $d\ge 2$.

With either result, Multidimensional Knapsack is para-NP-hard with respect to $d$. Thus, it is unlikely that Multidimensional Knapsack is in the class XP w.r.t. the dimension $d$.


---

