WORK AND MEMORY-EFFICIENT PARALLEL ALGORITHMS FOR THE KNAPSACK-PROBLEM

Parallel algorithms for solving a knapsack problem of size n on PRAM a nd distributed memory machines are presented. The algorithms are work- efficient in the sense that they achieve optimal speedup with regard t o the best known solution to this problem. Moreover, they match the be st current time/memory/processors tradeoffs, while requiring less memo ry and/or processors. Since the PRAM is considered mainly as a theoret ical model, and we want to produce practical algorithms for the knapsa ck problem, its solution in distributed memory machines is also studie d. For the first time in literature, work-efficient parallel algorithm s on local memory - message passing architectures - are given. Time bo unds for solving the problem on linear arrays, meshes, and hypercubes are proved.