A PARALLEL ALGORITHM FOR THE KNAPSACK-PROBLEM USING A GENERATION AND SEARCHING TECHNIQUE

被引：14

作者：

CHANG, HKC

CHEN, JJR

SHYU, SJ

机构：

来源：

PARALLEL COMPUTING | 1994年 / 20卷 / 02期

关键词：

KNAPSACK PROBLEM; SHARED MEMORY MULTIPROCESSOR; SIMD MACHINE; PARALLEL ALGORITHM; PERFORMANCE ANALYSIS;

D O I：

10.1016/0167-8191(94)90083-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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(2n/4) memory and O(2n/8) processors to find a solution for the knapsack problem of n components in time O(2n/2). The proposed parallel algorithm has a cost of O(2(5n/8)) which is an improved result over the past researches.

引用

页码：233 / 243

页数：11

共 15 条

[1]

Akl S. G., 1989, DESIGN ANAL PARALLEL

[2] TIME MEMORY PROCESSOR TRADE-OFFS [J].