Naslov
Monte-Carlo randomized algorithm for minimum feedback arc set

Autori
Kudelić, Robert

Izvornik
Applied soft computing (1568-4946) 41 (2016); 235-246

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Minimum feedback arc set ; Monte Carlo ; Randomization ; NP-hard ; NP-complete ; APX-hard

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo, Informacijske i komunikacijske znanosti

POVEZANOST RADA