Journal of Computer Science and Technology ›› 1986, Vol. 1 ›› Issue (1): 46-50.

Previous Articles     Next Articles

The Complexity of the 0/1 Multi-knapsack Problem

Zhang Li’ang1 and Geng Suyun2   

  1. 1Beijing Institute of Chemical Fibre Engineering, Beijing, China
    2Beijing University, Beijing, China
  • Received:1983-03-01 Online:1986-01-10 Published:2022-01-20

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.



[1] M.R. Garey and D.S. Johnson, A Guide to the Theory of NP-Completeness, W.H.Freeman and Company, San Francisco, 1979.
[2] M.R. Garey and D.S. Johnson, Complexity Results for Multiprocessor Scheduling under Resource Constraints.SIAM J. Computing,4 (1975), 397–411.
[3] M.R. Garey and D.S. Johnson, Strong NP-Completeness Results: Motivation, Examples, and Implications,J. Assoc. Comput. Mach.,25(1978), 499–508.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved