@inbook{6096fb4173204fdca87b994bf0394612,

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 complexities 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 Ω(log n) even if k is {"}large{"} i.e. k = n-c for some constant c ≥ 0. - Let 1 ≤ 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 ln(a/k) when a/k is at least about e2 ≈7.39, and for smaller values of a/k it decreases towards 2 exponentially with increasing 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 β followed by a greedy solution for the remaining problem.",

author = "Piotr Berman and Bhaskar DasGupta and Eduardo Sontag",

year = "2004",

doi = "10.1007/978-3-540-27821-4_4",

language = "English (US)",

isbn = "3540228942",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "39--50",

editor = "Klaus Jansen and Sanjeev Khanna and Rolim, {Jose D. P.} and Dana Ron",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}