HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Efficient linear systolic array for the knapsack problem

Rumen Andonov 1 Patrice Quinton 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : A processor-efficient systolic algorithm for the dynamic programming approach to the knapsack problem is presented in this paper. The algorithm is implemented on a linear systolic array where the number of cells q, the cell memory storage a and the input/output requirements are design parameters. These are independent of the problem size given by the number of the objects m and the knapsack capacity c. The time complexity of the algorithm is Q(mc/q+m) and both the time speedup and the processor efficiency are asymptotically optimal. A new procedure for the backtracking phase of the algorithm with a time complexity Q(m) is also proposed. It is an improvement on the usual strategies used for back-tracking which have a time complexity Q(m+c).
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:49:39 PM
Last modification on : Friday, February 4, 2022 - 3:23:02 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:57:51 PM


  • HAL Id : inria-00074896, version 1


Rumen Andonov, Patrice Quinton. Efficient linear systolic array for the knapsack problem. [Research Report] RR-1661, INRIA. 1992. ⟨inria-00074896⟩



Record views


Files downloads