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.
Type de document :
Rapport
[Research Report] RR-2037, INRIA. 1993
Liste complète des métadonnées


https://hal.inria.fr/inria-00074634
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:57:38
Dernière modification le : vendredi 13 janvier 2017 - 14:16:36
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:12:42

Fichiers

Identifiants

  • HAL Id : inria-00074634, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

335

Téléchargements du document

420