2
$\begingroup$

The paper _Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But MKP is strongly NP-hard, so it cannot have an FPTAS unless P=NP. Is the result of this paper wrong?

$\endgroup$
1
$\begingroup$

The paper you cite is not available to me. However, according to this paper: "Improved Fully Polynomial time Approximation Scheme for the 0-1 Multiple-choice Knapsack Problem",

0-1 MCKP is $\text{NP}$-hard [4] as it contains the 0-1 Knapsack problem as a special case [5, 13] but it can be solved in pseudo-polynomial time (emphasis added) through dynamic programming [7, 2].

Thus, 0-1 MCKP is not strongly $\text{NP}$-hard.

One of the citations is

[7] K. Dudzinski, S. Walukiewicz, “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, (28), (1987): 3–21.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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