Dynamic programming parallel implementations for the knapsack problem

Rumen Andonov (1) , Frédéric Raimbault (1) , Patrice Quinton (1)

1 API - Parallel VLSI Architectures

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.

Domaines: Autre [cs.OH]

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