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