Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4634734 | Applied Mathematics and Computation | 2008 | 9 Pages |
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
Xiaofan Yang, Qing Lu, Chuandong Li, Xiaofeng Liao,