Robinson, editors, Nonlinear Programming, volume 4, pages 415-437. On the existence of fast approximation schemes. In Mathematical Foundations o f Computer Science, volume 74 of Lecture Notes in Computer Science, pages 292-300. Computational complexity of approximation algorithms for combinatorial problems. 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. 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. 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). The Knapsack Problems text by Kellerer et al. I hope that I did not mess up anything in my definitions. 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. 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. 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). I would be happy for a proof of either of the two to be hard (hardness of the other should follow easily). Multidimensional knapsack tries to maximize $\sum_j c_j x_j$ such that $\sum_j a_$, the 0/1-version of the problem. 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. 4.2) many actually cite Garey & Johnson as "An introduction to" instead of "A guide to", so these authors probably copied from one another. 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.
0 kommentar(er)
