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

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-1\). -- We observe that the standard greedy algorithm produces an approximation ratio of \(\Omega(\log n)\) even if \(k\) is ``large'' i.e \(k=n-c\) for some constant \(c>0\). -- Let \(1<a<n\) denote the maximum number of elements in any given set in our set multicover problem. Then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio \(\mathbf E[r(a,k)]\) that is an increasing function of \(a/k\). The behavior of \(\mathbf E[r(a,k)]\) is roughly as follows: it is about \(\ln(a/k)\) when \(a/k\) is at least about \(\mathbf e^2\approx 7.39\), and for smaller values of \(a/k\) it decreases towards 1 as a linear function of \(\sqrt{a/k}\) with \(\lim_{a/k\to 0}\mathbf E[r(a,k)]=1\). Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity \(\beta\) followed by a greedy solution for the remaining problem. We also comment about the impossibility of a significantly faster convergence of \(\mathbf E[r(a,k)]\) towards 1 for any polynomial-time approximation algorithm.