The complexity of the 0/1 multi-knapsack problem. (English) Zbl 0593.68036
Summary: In this paper complexity of the 0/1 multi-knapsack problem is discussed. First we prove that the corresponding decision problem is NP-complete in the strong sense. For any fixed number k of knapsacks, the problem is only NP-complete in the ordinary sense, but not NP-complete in the strong sense. Then, we prove that the 0/1 multi-knapsack optimization problem is NP-equivalent by using Turing reduction.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | M.R. Garey and D.S. Johnson, A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, San Francisco, 1979. · Zbl 0411.68039 |
| [2] | M.R. Garey and D.S. Johnson, Complexity Results for Multiprocessor Scheduling under Resource Constraints.SIAM J. Computing,4 (1975), 397–411. · Zbl 0365.90076 · doi:10.1137/0204035 |
| [3] | M.R. Garey and D.S. Johnson, Strong NP-Completeness Results: Motivation, Examples, and Implications,J. Assoc. Comput. Mach.,25(1978), 499–508. · Zbl 0379.68035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
