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

fYear

2007

fDate

22-24 Feb. 2007

Firstpage

218

Lastpage

221

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICSCN.2007.350734

Filename

4156616