Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks (Q876471)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
scientific article

    Statements

    Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks (English)
    0 references
    0 references
    0 references
    0 references
    18 April 2007
    0 references
    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 \(\Omega(\log n)\) 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 approximation ratio \(\mathbf E[r(a,k)]\) that is an increasing function of \(a/k\). The behavior of \(\mathbf E[r(a,k)]\) is roughly as follows: it is about \(\ln(a/k)\) when \(a/k\) is at least about \(\mathbf e^2\approx 7.39\), and for smaller values of \(a/k\) it decreases towards 1 as a linear function of \(\sqrt{a/k}\) with \(\lim_{a/k\to 0}\mathbf E[r(a,k)]=1\). 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. We also comment about the impossibility of a significantly faster convergence of \(\mathbf E[r(a,k)]\) towards 1 for any polynomial-time approximation algorithm.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    set multicover
    0 references
    randomized approximation algorithms
    0 references
    reverse engineering
    0 references
    biological networks
    0 references
    0 references