@inproceedings{772bfb3ab583440fa3550ca71b01065d,
title = "Adaptive and cost-optimal parallel algorithm for the 0-1 knapsack problem",
abstract = "The 0-1 knapsack problem is well know to be NP-complete problem. In the past two decades, much effort has been done in order to find techniques that could lead to algorithms with a reasonable running time. This paper proposes a new parallel algorithm for the 0-1 knapsack problem where the optimal merging algorithm is adopted. Based on an EREW PRAM machine with shared memory, the proposed algorithm utilizes O((2(n/4))(1-e)) processors, 0 \textbackslash{}le \textbackslash{}le 1, and O(2(n/2)) memory to find a solution for the n-element 0-1 knapsack problem in time O((2(n/4))(2(n/4))e). Thus the cost of the proposed parallel algorithm is O(2(n/2)), which is both the lowest upper-bound time and without memory conflicts if only quantity of objects is considered in the complexity analysis for the 0-1 knapsack problem. Thus it is an improvement result over the past researches.",
keywords = "0-1 knapsack problem, EREW PRAM, combinatorial optimization, divide and conquer, parallel computing",
author = "Kenli Li and Lingxiao Li and Teklay Tesfazghi and Sha, \{Edwin Hsing Mean\}",
year = "2011",
doi = "10.1109/PDP.2011.11",
language = "英语",
isbn = "9780769543284",
series = "Proceedings - 19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing, PDP 2011",
pages = "537--544",
booktitle = "Proceedings - 19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing, PDP 2011",
note = "19th International Euromicro Conference on Parallel, Distributed, and Network-Based Processing, PDP 2011 ; Conference date: 09-02-2011 Through 11-02-2011",
}