DocumentCode
1947039
Title
Notice of Retraction
Improved dynamic programming algorithms for the 0–1 knapsack problem
Author
Xiaohua Meng ; Yue-an Zhu ; Xiaoming Wu
Author_Institution
Sch. of Comput. Sci. & Eng., South China Univ. of Technol., Guangzhou, China
Volume
8
fYear
2010
fDate
9-11 July 2010
Firstpage
19
Lastpage
22
Abstract
Notice of Retraction
After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.
We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.
The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.
Based on the classic dynamic programming solution to solve the 0-1 knapsack problem, we give an improved algorithm called IKP. Further, in order to decrease the space complexity of IKP, we combine divided-and-conquered strategy with IKP to obtain a new algorithm DKP. Our Analysis shows that DKP has a great advantage over IKP in running time and resource cost. Moreover, DKP has a better time complexity than some known algorithms for the 0-1 knapsack problem, and it has high parallel, in which way DKP can relief the tension of memory cost.
After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.
We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.
The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.
Based on the classic dynamic programming solution to solve the 0-1 knapsack problem, we give an improved algorithm called IKP. Further, in order to decrease the space complexity of IKP, we combine divided-and-conquered strategy with IKP to obtain a new algorithm DKP. Our Analysis shows that DKP has a great advantage over IKP in running time and resource cost. Moreover, DKP has a better time complexity than some known algorithms for the 0-1 knapsack problem, and it has high parallel, in which way DKP can relief the tension of memory cost.
Keywords
computational complexity; divide and conquer methods; dynamic programming; knapsack problems; 0-1 knapsack problem; divided-and-conquered strategy; dynamic programming algorithm; space complexity; time complexity; Lead; 0–1 knapsack problem; algorithm complexity; divided-and-conquer; dynamic programming;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference on
Conference_Location
Chengdu
Print_ISBN
978-1-4244-5537-9
Type
conf
DOI
10.1109/ICCSIT.2010.5564469
Filename
5564469
Link To Document