A parallel algorithm for the knapsack problem using a generation and searching technique

Henry Ker Chang Chang*, Jonathan Jen Rong Chen, Shyong Jian Shyu

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

18 Scopus citations

Abstract

The purpose of this paper is to propose a new parallel algorithm for the knapsack problem. We develop a generation and searching technique to derive the desired two ordered lists in the preliminary process of the general knapsack problem. The proposed parallel algorithm is developed on the basis of an SIMD machine with shared memory. The algorithm needs O(2 n 4) memory and O(2 n 8) processors to find a solution for the knapsack problem of n components in time O(2 n 2). The proposed parallel algorithm has a cost of O(2 5n 8) which is an improved result over the past researches.

Original languageEnglish
Pages (from-to)233-243
Number of pages11
JournalParallel Computing
Volume20
Issue number2
DOIs
StatePublished - 02 1994
Externally publishedYes

Keywords

  • Knapsack problem
  • Parallel algorithm
  • Performance analysis
  • SIMD machine
  • Shared memory multiprocessor

Fingerprint

Dive into the research topics of 'A parallel algorithm for the knapsack problem using a generation and searching technique'. Together they form a unique fingerprint.

Cite this