Monte-carlo randomized algorithm for minimal feedback arc set problem

R Kudelić - Applied soft computing, 2016 - Elsevier
Applied soft computing, 2016Elsevier
When we are developing information system we must, in some way, determine the
development order of its subsystems. Currently, this problem is not formally solved.
Therefore, to rectify this we are proposing a solution which takes the sum of weights of
feedback arcs as a criteria for determining the development order, rather than some other
criteria that has not come directly from information system description. For the purpose of
solving this problem we have developed, analyzed, and tested, Branch and Bound algorithm …
Abstract
When we are developing information system we must, in some way, determine the development order of its subsystems. Currently, this problem is not formally solved. Therefore, to rectify this we are proposing a solution which takes the sum of weights of feedback arcs as a criteria for determining the development order, rather than some other criteria that has not come directly from information system description. For the purpose of solving this problem we have developed, analyzed, and tested, Branch and Bound algorithm and Monte-Carlo randomized algorithm which solves the problem of Information System Subsystems Development Order in polynomial time with arbitrary probability. Also, we have determined an approximation error for developed Monte-Carlo randomized algorithm. Lastly, we have proven that the problem of Information System Subsystems Development Order is NP-hard, NP-complete, and APX-hard.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果