Name
Title | ||
|---|---|---|
Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks |
Abstract | ||
|---|---|---|
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 (logn) 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 approxima- tion 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 ln(a/k) when a/k is at least about e2 7.39, and for smaller values of a/k it decreases towards 1 as a linear function of p a/k with lima/k!0 E(r(a,k)) = 1. Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity followed by a greedy solution for the remaining prob- lem. We also comment about the impossibility of a significantly faster convergence of E(r(a,k)) towards 1 for any polynomial-time approximation algorithm. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2004.11.009 | Discrete Applied Mathematics |
Keywords | Field | DocType |
set multicover,following problem,reverse engineering,positive example,biological networks,computational molecular biology,multicover problem,position-specific score matrix,various problem,negative example,gene network,randomized approximation algorithms,randomized approximation algorithm,computational complexity,randomized rounding,greedy algorithm,biological network,randomized algorithm | Approximation algorithm,Binary logarithm,Discrete mathematics,Randomized algorithm,Combinatorics,Parameterized complexity,Greedy algorithm,Randomized rounding,Time complexity,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
155 | 6-7 | Discrete Applied Mathematics |
Citations | PageRank | References |
23 | 2.25 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piotr Berman | 1 | 1754 | 192.48 |
| Bhaskar DasGupta | 2 | 551 | 70.14 |
| Eduardo D. Sontag | 3 | 3134 | 781.88 |