Analyzing Time Complexity of Parallel Algorithms for Knapsack Problem

摘要

In this paper, we have analyzed various parallel algorithms for solving knapsack problem and proposed an efficient approach for solving knapsack problem using an approximation algorithm. We also discussed the time complexity of different algorithm. Backtracking is not discussed here due to it's inherent sequential property. The validity of the proposed algorithm is demonstrated on a worked out example and it shows the superiority of the proposed algorithm.