Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420698 | Discrete Applied Mathematics | 2007 | 17 Pages |
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-1k=n-1.••We observe that the standard greedy algorithm produces an approximation ratio of Ω(logn)Ω(logn) even if k is “large” i.e k=n-ck=n-c for some constant c>0c>0.••Let 1
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Piotr Berman, Bhaskar DasGupta, Eduardo Sontag,