Multidimensional knapsack STRONGLY NP-complete 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 &amp; Johnson, although it is not in their list of strongly NP-complete problems (Sec. 4.2); many actually cite Garey &amp; 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 0–1 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...
In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (http://epubs.siam.org/doi/abs/10.1137/S0097539799356265) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not fixed. You can find hardness results as function of d in that paper.