| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4627474 | Applied Mathematics and Computation | 2014 | 8 Pages |
Abstract
The assignment problem (AP) is to optimally solve the task of assigning n jobs to n individuals, such that minimum cost or maximum profit can be obtained. It is a vitally important NP-complete problem in operation management and applied mathematics, having a wide range of applications. In this paper, we present a new parallel DNA algorithm to solve the assignment problem using DNA molecular operations. Meanwhile, we design flexible length DNA strands to represent different jobs and individuals, take appropriate steps and get the solutions of the AP in proper length range and with O(n2)O(n2) time complexity. We extend the application of DNA molecular operations and simultaneity reduce the complexity of the computation.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Zhaocai Wang, Jian Tan, Dongmei Huang, Yingchao Ren, Zuwen Ji,