Old Web
The complexity of the 0/1 multi-knapsack problem
1986
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 numberk 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.
Keywords:
- Polynomial-time reduction
- Computer science
- Continuous knapsack problem
- P-complete
- Mathematical optimization
- Generalized assignment problem
- Function problem
- Cutting stock problem
- co-NP-complete
- Maximum common subgraph isomorphism problem
- P versus NP problem
- Computational problem
- Computational complexity theory
- Knapsack problem
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
4
References
12
Citations
NaN
KQI