A PARALLEL 2-LIST ALGORITHM FOR THE KNAPSACK-PROBLEM

An n-element knapsack problem has 2(n) possible solutions to search ov er, so a task which can be accomplished in 2(n) trials if an exhaustiv e search is used. Due to the exponential time in solving the knapsack problem, the problem is considered to be very hard. In the past decade , much effort has been done in order to find techniques which could le ad to practical algorithms with reasonable running time. In 1994, Chan g et al. proposed a brilliant parallel algorithm, which needs O(2(n/8) ) processors to solve the knapsack problem in O(2(n/2)) time; that is, the cost of Chang et al.'s parallel algorithm is O(2(5n/8)). In this paper, we propose a parallel algorithm to improve Chang et al.'s paral lel algorithm by reducing the time complexity to be O(2(3n/8)) under t he same O(2(n/8)) processors available. Thus, the proposed parallel al gorithm has a cost of O(2(n/2)). It is an improvement over previous li terature. We believe that the proposed parallel algorithm is pragmatic ally feasible at the moment when multiprocessor systems become more an d more popular.