DIMACS TR: 2004-10

Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks

Authors: Piotr Berman, Bhaskar DasGupta and Eduardo Sontag


(This paper improves the results in DIMACS TR 2004-01)

In this paper we investigate the computational complexities of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows:

(1) 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.

(2) 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.

(3) Let a<n denotes 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 E[r(a,k)] that is an increasing function of a/k. The behavior of E[r(a,k)] is ``roughly'' as follows: it is about 1+ln(a/k) when a/k is at least about $e^2, and for smaller values of a/k it decreases towards 2 linearly with decreasing a/k with lim_{a/k-->0} E[r(a,k)] <= 2. 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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-10.ps.gz

DIMACS Home Page