A SYSTOLIC ALGORITHM FOR SOLVING KNAPSACK-PROBLEMS

doi:10.1080/00207169408804335

Title:	A SYSTOLIC ALGORITHM FOR SOLVING KNAPSACK-PROBLEMS
Authors:	LIN, CJ CHEN, SJ 應用數學系 Department of Applied Mathematics
Keywords:	SYSTOLIC ARRAY;PARALLEL ALGORITHM;TREE;KNAPSACK PROBLEM
Issue Date:	1994
Abstract:	A systolic algorithm for solving the O/1-knapsack problems with n items is presented. The computational model used is a tree structure which consists of 2(n) identical processing elements (PEs). Each PE executes the same program at any time step. The time complexity varies from n to 3n - 2 steps which includes all the input/output data communication time. The design process and the correctness verification of this algorithm are considered in detail.
URI:	http://hdl.handle.net/11536/2703 http://dx.doi.org/10.1080/00207169408804335
ISSN:	0020-7160
DOI:	10.1080/00207169408804335
Journal:	INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
Volume:	54
Issue:	1-2
Begin Page:	23
End Page:	32
Appears in Collections:	Articles