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

Piotr Berman, Bhaskar DasGupta, Eduardo Sontag

    Research output: Chapter in Book/Report/Conference proceedingChapter

    12 Scopus citations

    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.

    Original languageEnglish (US)
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    EditorsKlaus Jansen, Sanjeev Khanna, Jose D. P. Rolim, Dana Ron
    PublisherSpringer Verlag
    Pages39-50
    Number of pages12
    ISBN (Print)3540228942, 9783540228943
    DOIs
    StatePublished - 2004

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume3122
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks'. Together they form a unique fingerprint.

    Cite this