Computational study demonstrates a parallel DNA algorithm solving the assignment problem in linear time, indicating a scalable molecular framework for NP-hard combinatorial optimization.
BACKGROUND: Many problems of combinatorial optimization, which are solvable only in exponential time, are known to be Non-Deterministic Polynomial hard (NP-hard). With the advent of parallel machines, new opportunities have been emerged to develop the effective solutions for NP-hard problems. However, solving these problems in polynomial time needs massive parallel machines and is not applicable up to now. OBJECTIVES: DNA (Deoxyribonucleic acid) computing provides a fantastic method to solve NP-hard problems in polynomial time. Accordingly, one of the famous NP-hard problems is assignment problem, which is designed to find the best assignment of n jobs to n persons in a way that it could maximize the profit or minimize the cost. MATERIAL AND METHODS: Applying bio molecular operations of Adelman Lipton model, a novel parallel DNA algorithm have been proposed for solving the assignment problem. RESULTS: ) initial DNA strand in comparison with nn initial sequence, which is used by the other methods. CONCLUSIONS: In this article, using DNA computing, we proposed a parallel DNA algorithm to solve the assignment problem in linear time.
No takes yet. Share an insight, caveat, or question.
Khorsand et al. (2020) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: