We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 1 Issue 1
January  1986
Turn off MathJax
Article Contents
Abstract
References
Zhang Li’ang, Geng Suyun. The Complexity of the 0/1 Multi-knapsack Problem[J]. Journal of Computer Science and Technology, 1986, 1(1): 46-50.
Citation: Zhang Li’ang, Geng Suyun. The Complexity of the 0/1 Multi-knapsack Problem[J]. Journal of Computer Science and Technology, 1986, 1(1): 46-50.
shu

The Complexity of the 0/1 Multi-knapsack Problem

  • 1Beijing Institute of Chemical Fibre Engineering, Beijing, China
    2Beijing University, Beijing, China

More Information
  • Received Date: February 28, 1983
  • Published Date: January 09, 1986
    Abstract
  • 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.



    • FullText(HTML)
    • References (3)
  • [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.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (22) PDF downloads (18) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return