Title :
Analyzing Time Complexity of Parallel Algorithms for Knapsack Problem
Author :
Padmavathi, S. ; Shalinie, S. Mercy
Author_Institution :
Dept. of Comput. Sci. & Eng., Thiagarajar Coll. of Eng., Madurai
Abstract :
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 its 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
Keywords :
computational complexity; dynamic programming; knapsack problems; parallel algorithms; approximation algorithm; backtracking; dynamic programming; knapsack problem; parallel algorithms; polynomial time; time complexity analysis; Algorithm design and analysis; Approximation algorithms; Computational efficiency; Concurrent computing; Dynamic programming; Heuristic algorithms; Large-scale systems; Parallel algorithms; Polynomials; Topology; Dynamic programming; Parallel algorithm; approximation algorithm; polynomial time;
Conference_Titel :
Signal Processing, Communications and Networking, 2007. ICSCN '07. International Conference on
Conference_Location :
Chennai
Print_ISBN :
1-4244-0997-7
Electronic_ISBN :
1-4244-0997-7
DOI :
10.1109/ICSCN.2007.350734
