Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found another load where they cite Garey & Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey & Johnson as An introduction to instead of A guide to, so these authors probably copied from one another. In fact, some authors claim that it is not strongly NP-complete, an example is The multidimensional 01 knapsack problem: An overview by Freville, but the argument (generalize the DP for single-dimension knapsack) is obviously bogus, see below.Multidimensional knapsack tries to maximize $\sum_j c_j x_j$ such that $\sum_j a_{ij} x_j \le b_j$ for $i=1,...,m$, with $x_i$ being integer $\ge 0$ (and all $c_j, a_{ij}, b_j$ being $\ge 0$). We can also demand $x_i \in \{0,1\}$, the 0/1-version of the problem. I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily).Strongly NP-hard applies only to number problems, and restricts the (some) maximum of the numbers to be polynomial in the size of the problem instance (bits needed to encode it). Strongly NP-hard rules out the existence of a pseudopolynomial algorithm for the problem, with running time polynomial in the numbers that appear in the instance. The usual knapsack (single-dimensional) obviously has a pseudopolynomial algorithm (DP), but this algorithm cannot be generalized to multidimensional KP, as the dimension of the KP appears in the exponent of the running time. I hope that I did not mess up anything in my definitions...
Multidimensional knapsack STRONGLY NP-complete
reference request;np hardness