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

Dynamic programming parallel implementations for the knapsack problem

Rumen Andonov 1 Frédéric Raimbault 1 Patrice Quinton 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : A systolic algorithm for the dynamic programming approach to the knapsack problem is presented. The algorithm can run on any number of processors and has optimal time speedup and processor efficiency. The running time of the algorithm is [??](mc/q+m) on a ring of q processors, where c is the knapsack size and m is the number of object types. A new procedure for the backtracking phase of the algorithm with a time complexity [??](m) is also proposed which is an improvement on the usual strategiesused for backtracking with a time complexity [??](m+c). Given a practical implementations, our analysis shows which of two backtracking algorithms (the classical or the modified) is more efficient with respect to the total running time. Experiments have been performed on an iWARP machine for randomly generated instances. They support the theoretical results and show the proposed algorithm performs well for a wide range of problem size.
Document type :
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 3:57:38 PM
Last modification on : Friday, February 4, 2022 - 3:24:36 AM
Long-term archiving on: : Monday, April 5, 2010 - 12:12:42 AM


  • HAL Id : inria-00074634, version 1


Rumen Andonov, Frédéric Raimbault, Patrice Quinton. Dynamic programming parallel implementations for the knapsack problem. [Research Report] RR-2037, INRIA. 1993. ⟨inria-00074634⟩



Record views


Files downloads