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

Abstract:

Article Preview

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 and 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:

$35.00

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

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