Paper Title:
Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation
  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.

  Info
Periodical
Edited by
Qi Luo
Pages
1767-1772
DOI
10.4028/www.scientific.net/AMM.58-60.1767
Citation
K. R. Wu, C. W. Yeh, "Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation", Applied Mechanics and Materials, Vols. 58-60, pp. 1767-1772, 2011
Online since
June 2011
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

Authors: Kie Jin Lee, Arsen Babajayan, Song Hui Kim
Abstract:A near-field scanning microwave microscope (NSMM) is used to study the physical properties of DNA strands with a specific sequence and image...
1040
Authors: Lian Ye, Jing Chen, Yong Kang Xing
Abstract:DNA sequence design is the basic and important step for DNA computing. Good codeword could avoid some error may possibly occurred in...
94
Authors: Sheng Jun Xue, Wei Qi
Abstract:Traditional resource scheduling algorithm, in grid environment, exist some defects, for example it can not well meet the quality requirements...
1594
Authors: Guang Nian Yang, Wei Qi, Jun Zhou
Abstract:Now, our sewage treatment industry mainly depends on the blower of aeration act as metabolic, absorbed in the toxic substances. Blower...
591
Authors: Yan Yang, Zhi Xiang Yin
Chapter 3: Mechatronics and Automation
Abstract:About thirty years ago, the concept of the complexity of the problem was proposed. The most important complex class is P and NP class....
1729