A parallel two-list algorithm for the knapsack problem |
| |
Authors: | Der-Chyuan Lou Chin-Chen Chang |
| |
Affiliation: | Institute of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, ROC |
| |
Abstract: | An n-element knapsack problem has 2n possible solutions to search over, so a task which can be accomplished in 2″ trials if an exhaustive 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 lead to practical algorithms with reasonable running time. In 1994, Chang et al. proposed a brilliant parallel algorithm, which needs O(2n/8) processors to solve the knapsack problem in O(2n/2) time; that is, the cost of Chang et al.'s parallel algorithm is O(25n/8). In this paper, we propose a parallel algorithm to improve Chang et al.'s parallel algorithm by reducing the time complexity to be O(23n/8) under the same O(2n/8) processors available. Thus, the proposed parallel algorithm has a cost of O(2n/2). It is an improvement over previous literature. We believe that the proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular. |
| |
Keywords: | Knapsack problem NP-complete problems Parallel algorithms Cryptosystem |
本文献已被 ScienceDirect 等数据库收录! |
|