Monte-Carlo randomized algorithm for minimal feedback arc set problem

• To solve the problem of Information System Subsystem Development Order we are proposing a solution which takes sum of weights of feedback arcs as a criteria for determining development order rather than some other criteria which has not come directly from information system description.
• We have proven that this problem is NP-hard, NP-complete and APX-hard.
• For the purpose of solving this problem efficiently we have developed, analyzed and tested Monte Carlo randomized algorithm.

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.

Figure optionsDownload as PowerPoint slide