Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks

In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows:
•
• We abstract a combinatorial version of the problem and observe that this is “equivalent” to the set multicover problem when the “coverage” factor k is a function of the number of elements n   of the universe. An important special case for our application is the case in which k=n-1k=n-1.
•
• We observe that the standard greedy algorithm produces an approximation ratio of Ω(logn)Ω(logn) even if k   is “large” i.e k=n-ck=n-c for some constant c>0c>0.
•
• Let 1