For Libraries For Publication Open Access Downloads About Us Contact Us
Paper Titles
Wood Recognition Based on Histogram Matching Algorithms
p.1744
Research on Modeling Virtual Battlefield Based-On Ontology
p.1749
A Modified Box-Counting Method to Estimate the Fractal Dimensions
p.1756
Research on Three-Dimensional Digitization Method of General Cliff Petroglyph in Lianyungang City
p.1762
Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation
p.1767
New Evolutionary Neural Network Based on Continuous Ant Colony Optimization
p.1773
Identifying Transformer Inrush Current Based on Artificial Neural Network
p.1779
A Research on Rapid Modeling Technique of Virtual Reality 3-Dimentional Underground Piping
p.1786
A Study of a New ELID Grinding Fluid by BP Neural Network Model
p.1792

Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation

Article Preview

Abstract:

We proposed a two-layer scheme of Deoxyribonucleic acid (DNA) based computation, DNA-01MKP, to solve the typical NP-hard combinatorial optimization problem, 0-1 multidimensional knapsack problem (0-1 MKP). DNA-01MKP consists of two layers of procedures: (1) translation of the problem equations to strands and (2) solution of problems. For layer 1, we designed flexible well-formatted strands to represent the problem equations; for layer 2, we constructed the DNA algorithms to solve the 0-1 MKP. Our results revealed that this molecular computation scheme is able to solve the complicated operational problem with a reasonable time complexity of O(n×k), though it needs further experimental verification in the future. By adjusting the DNA-based procedures, the scheme may be used to resolve different NP-hard problems.

You might also be interested in these eBooks
Information Technology for Manufacturing Systems II View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 58-60)

Pages:

1767-1772

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.58-60.1767

Citation:

Cite this paper

Online since:

June 2011

Authors:

Kee Rong Wu, Chung Wei Yeh

Keywords:

0-1 Knapsack Problems, DNA Computation, DNA Encoding, NP Hard Problem

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2011 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

[1] L. Adleman: Science Vol. 266 (1994), p.1021.

Google Scholar

[2] B. Yurke, A.P. Mills Jr. and S.L. Cheng: BioSystems Vol. 52 (1999), p.165.

Google Scholar

[3] F. Guarnieri, F. Makiko, and C. Bancroft: Science Vol. 273 (1996), p.220.

Google Scholar

[4] S. Roweis, E. Winfree, R. Burgoyne, N.V. Chelyapov, M.F. Goodman, L. Adleman, P. Rothemund: J. Comp. Biology, Vol. 5(4) (1998), p.615.

DOI: 10.1089/cmb.1998.5.615

Google Scholar

[5] M. Amos, Theoretical and experimental DNA computation (Springer, 2004).

Google Scholar

[6] R. Beigel, and B. Fu: IEEE Conference on Computational Complexity (1998), p.11.

Google Scholar

[7] R.J. Lipton: Science Vol. 268 (1995), p.542.

Google Scholar

[8] C.V. Henkel, T. Bäck, J.N. Kok,G. Rozenberg and H.P. Spaink, BioSystems 88 (2007) p.156.

DOI: 10.1016/j.biosystems.2006.06.001

Google Scholar

[9] M. Darehmiraki and H.M. Nehi: Appl. Math. Comp. Vol. 187 (2007) p.1033.

Google Scholar

[10] G. Cui, C. Li, X. Zhang, Y. Wang, X. Qi, X. Li and H. Li: Lect. Notes Comp. Sci., Vol. 5553 (2009) p.684.

Google Scholar

[11] Y. Wang, W. Lu, X. Zhang, G. Cui: 2010 IEEE Fifth International Conference on Bio-Inspired Computing, Sept, 23-26, 2010, Changsha, China, p.180.

Google Scholar

[12] Fu B, Beigel R, Zhou: Biosystems Vol. 52(1-3) (1999), p.217.

Google Scholar

[13] C.W. Yeh, C.P. Chu and K.R. Wu: Biosystems Vol. 83 (2006), 56-66.

Google Scholar

© 2025 Trans Tech Publications Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. For open access content, terms of the Creative Commons licensing CC-BY are applied.
Scientific.Net is a registered trademark of Trans Tech Publications Ltd.