Article ID Journal Published Year Pages File Type
4634734 Applied Mathematics and Computation 2008 9 Pages PDF
Abstract
Biological computing provides a promising approach to attacking computationally intractable problems. The quadratic assignment problem (QAP) is a well-known NP-hard combinatorial optimization problem. This paper addresses the problem of how to solve QAP under the Adleman-Lipton-sticker model. A theoretically efficient DNA algorithm for solving QAP is proposed, which is executed by performing O(Kn4) operations on test tubes of DNA molecular strands with n2 + K + 1 bit regions, where n is the number of facilities, and K is the length of the binary representation of an upper bound on the objective function. With the rapid progress of molecular biology techniques, the proposed algorithm might be of practical use in treating medium-sized instances of QAP.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , , ,