## 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

**
ABSTRACT
**

(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