Parallelizing Assignment Problem with DNA Strands

Document Type: Research Paper


Computer Engineering Department, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran



Background: Many problems of combinatorial optimization are known to be Non-Deterministic Polynomial hard (NP-hard), which are solvable only in exponential time. With the advent of parallel machines, new opportunities have been emerged to develop effective solutions for NP-hard problems. However, solving these problems in polynomial time needs massive parallel machines and is not yet applicable.
Objectives: DNA (Deoxyribonucleic acid) computing provides a fantastic method in order to solve NP-hard problems in polynomial time. 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 maximize 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: The proposed algorithm solve the problem in O(n^2) time complexity and just O(n) initial DNA strand in comparison with n^n initial sequence which is used by the other methods.
Conclusions: In this article by using DNA computing, we propose a parallel DNA algorithm to solve the assignment problem in linear time.


Main Subjects