8
$\begingroup$

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 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...

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ The problem is NP-complete in the strong sens if the number of dimensions is a part of the input. If the number of dimensions is fixed then the problem is not strongly NP-complete. $\endgroup$
    – Lamine
    Commented Apr 2, 2014 at 7:49
  • $\begingroup$ Most problems become simpler if you fix any of their parameters. In other words, this observation is true but not helpful. Also see the discussion below. $\endgroup$
    – Sebastian
    Commented Apr 2, 2014 at 9:46
  • $\begingroup$ @Lamine citation? $\endgroup$
    – Austin Buchanan
    Commented Apr 2, 2014 at 14:42
  • 1
    $\begingroup$ @Sebastian: I agree with your answer below, a simple extension of the knapsack DP works for a fixed dimension $d$, with a running time of $O(W^d)$. The next question is whether it is $\sf{W[1]}$-hard when parameterized by $d$, it seems likely and would imply strong NP-completeness for unbounded $d$ isn't it? $\endgroup$
    – NisaiVloot
    Commented Apr 2, 2014 at 15:17
  • $\begingroup$ @AustinBuchanan First chapter of Pisinger's thesis. If the number of dimensions is fixed, the problem cannot be $\mathsf{NP}$-complete since it admits a pseudo-polynomial algorithm. $\endgroup$
    – Lamine
    Commented Apr 2, 2014 at 15:46

5 Answers 5

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

The Knapsack Problems text by Kellerer et al. cites the two references below as proving that multidimensional knapsack is strongly NP-hard already in the special case of CARDINALITY 2-KP (two-dimensional, with unit values). It also reproduces a proof, reducing from EQUIPARTITION, i.e., the existence of an FPTAS for CARDINALITY 2-KP implies that the EQUIPARTITION decision problem can be solved in polynomial time.

I believe the augmented resources version of the (fixed dimension) problem, where you're permitted to exceed the bounds by $\epsilon$ does admit an FPTAS, however.

G.Y. Gens and E.V. Levner. Computational complexity of approximation algorithms for combinatorial problems. In Mathematical Foundations o f Computer Science, volume 74 of Lecture Notes in Computer Science, pages 292-300. Springer, 1979.

B. Korte and R. Schrader. On the existence of fast approximation schemes. In O.L. Mangasarian, R.R. Meyer, and S.M. Robinson, editors, Nonlinear Programming, volume 4, pages 415-437. Academic Press, 1981.

Improve this answer
$\endgroup$
3
$\begingroup$

A possible reduction is from Exact Cover by Three Sets (X3C) (which is strongly NP-hard):

Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F_i = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}, i=1,...,m$ of 3-elements subsets of $X$ (triples);
Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

Reduction: given an instance of X3C, just pick a knapsack with $3n$ dimensions each one with maximum capacity $c_i = 1$; pick $n$ objects corresponding to the subsets $F_i$ with profit $1$ and assign weight $a_{ij} = 1$ if and only if $x_j$ is contained in set $F_i$. You can reach a total profit of $n$ if and only if the original X3C problem has a solution, i.e. you can fill the whole knapsack; the objects in the knapsack correspond to the subsets $F_i$ that form a valid exact cover of $X$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Darn, I should have looked there first... Thanks, that closes the question. (Still shocked that none of the OR publications I read got that one right.) $\endgroup$
    – Sebastian
    Commented Apr 1, 2014 at 15:35
  • $\begingroup$ Nope, looking more closely, this is not "it": Martello and Toth deal with the multi KP problem (you can sort the items into multiple knapsacks). But I am interested in the multidimensional KP: each item goes into all knapsacks simultaneously. For example, volume and mass of all items must both be below some given thresholds, but obviously, they are not connected. $\endgroup$
    – Sebastian
    Commented Apr 1, 2014 at 15:47
  • $\begingroup$ You're right, they deal with the multi KP. The reduction from X3C to multidimensional KP in the modified answer should work. $\endgroup$
    – Marzio De Biasi
    Commented Apr 2, 2014 at 8:13
2
$\begingroup$

I believe you could also reduce from bin-packing which is strongly NP-complete according to wikipedia.

Consider this instance of MD-KS: $$ \max \sum_{i = 1, j = 1}^{n, m} x_{i,j} \\ s.t.: \sum_{j} x_{i,j} \le 1 \\ \;\;\;\;\;\;\;\; \sum_{i} a_{i} x_{i,j} \le b \\ \;\;\;\;\;\;\;x_{i, j} \in \{0, 1 \} $$

The optimization problem above finds the maximum number of objects out of $n$ objects, which can be fit into $m$ bins of size $b$ (size/weight of object $i$) is $a_i$.

Bin Packing (decision problem): Given $n$ objects, can we fit them in $m$ bins? Solution: Run optimization above and return true if the optimal value is $n$. False otherwise.

The size of MD-KP here is $mn$ variables and $n + m$ constraints. The size of corresponding bin-packing problem is $n$ objects and $m$ bins. In any case, the sizes are polynomial-ly related so I believe the reduction is valid.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Presumably, @Sebastian is trying to show that the problem is strongly NP-hard with a constant number of constraints. $\endgroup$
    – Austin Buchanan
    Commented Apr 1, 2014 at 22:08
  • 1
    $\begingroup$ For fixed $m$, isn't the original problem polynomial in the length of input? Also, the original problem needs $O(nm)$ coefficients and so does the instance above. $\endgroup$
    – Ehsan
    Commented Apr 1, 2014 at 23:21
  • $\begingroup$ If you only wanted to show that the problem is strongly NP-hard for an arbitrary number of ''dimensions'', then yes your reduction works. I think it is more interesting to ask--does it remain strongly NP-hard in 2 or 3 ''dimensions''? $\endgroup$
    – Austin Buchanan
    Commented Apr 2, 2014 at 2:25
  • 2
    $\begingroup$ There are three lines in this wikipedia article that I find relevant to this discussion. The third line says and I quote "For any fixed m \ge 2, these problems do admit a pseudo-polynomial time algorithm (similar to the one for basic knapsack) and a PTAS.[2]". If this is true, then we the MD-KS is not strongly NP if "m" is a fixed number. Section (Multiple Constraints) of this: en.wikipedia.org/wiki/List_of_knapsack_problems $\endgroup$
    – Ehsan
    Commented Apr 2, 2014 at 19:53
2
$\begingroup$

Ok, let me try to answer this myself:

  • I was looking for a reference, not a proof. My hope was that it is in fact a two-line proof, and that I was just missing that. This seems to be true. The people who saw it, never wrote it up; everybody else just repeated the fact, without seeing the proof, I guess.
  • You can use reduction from any problem that can be formulated as an ILP with
    • polynomial number of constraints/variables,
    • only non-negative (integer) coefficients in the ILP formulation and objective function,
    • bounded maximum coefficient in the ILP is (either constant or some polynomial in the size of the instance), and
    • all constraints are $\le$.
  • Any problem that is NP-hard and does not involve numbers, is strongly NP-hard.
  • Just as (yet another) example, you can use the ILP formulation of maximum independent set as a multidimensional KP, where all coefficients are 0/1. This is the simplest ILP of any problem that I can think of.
  • This indeed results in a polynomial number of constraints (polynomial dimension), but:
  • For fixed dimension, there exists a polynomial DP algorithm for finding the best solution; so, it cannot be strongly NP-hard for fixed dimension (@Austin).

Is all of that correct? Then, sorry for the mess. Otherwise, please tell me if/where I am wrong...

Improve this answer
$\endgroup$
3
  • $\begingroup$ A reduction from vertex cover does not work, at least given your statement of multi-dimensional knapsack. The constraints should be of the $\le$ type. Max clique or set packing would work. $\endgroup$
    – Austin Buchanan
    Commented Apr 2, 2014 at 14:32
  • $\begingroup$ My fault, thanks. I have replaced vertex cover by maximum independent set, the other side of the coin. $\endgroup$
    – Sebastian
    Commented Apr 2, 2014 at 17:01
  • $\begingroup$ Multidimensional knapsack is essentially the same as what are called packing integer programs (PIPs) which captures max independent set as a special case, as you observe. $\endgroup$
    – Chandra Chekuri
    Commented May 19, 2015 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.