An exact algorithm for the weighed mutually exclusive maximum set cover problem
Lu, Songjian · Lu, Xinghua
Original · EN
In this paper, we introduce an exact algorithm with a time complexity of O*(1.325ᵐ) for the weighted mutually exclusive maximum set cover problem, where m is the number of subsets in the problem. This is an NP-hard motivated and abstracted from a bioinformatics problem of identifying signaling pathways based gene mutations. Currently, this problem is addressed using heuristic algorithms, which cannot guarantee the performance of the solution. By providing a relatively efficient exact algorithm, our approach will like increase the capability of finding better solutions in the application of cancer research.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.