Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
DOI10.1016/J.DAM.2004.11.009zbMATH Open1163.68045OpenAlexW2163141979MaRDI QIDQ876471FDOQ876471
Bhaskar Dasgupta, Eduardo D. Sontag, Piotr Berman
Publication date: 18 April 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2004.11.009
Recommendations
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Randomized approximation for the set multicover problem in hypergraphs
- Approximation algorithms for the maximum multiple RNA interaction problem
- Hypergraph covering problems motivated by genome assembly questions
- On Approximating an Implicit Cover Problem in Biology
- Tight approximability results for test set problems in bioinformatics
- Algorithm Theory - SWAT 2004
- Exact algorithms for set multicover and multiset multicover problems
- Approximating the maximum multiple RNA interaction problem
Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Randomized algorithms (68W20) Approximation algorithms (68W25)
Cites Work
- A threshold of ln n for approximating set cover
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Enumeration of Seven-Argument Threshold Functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Inference of signaling and gene regulatory networks by steady-state perturbation experiments: structure and accuracy
Cited In (16)
- On Approximating an Implicit Cover Problem in Biology
- Randomized approximation for the set multicover problem in hypergraphs
- Parameterized complexity of \(d\)-hitting set with quotas
- Approximating the online set multicover problems via randomized winnowing
- Randomized Online Algorithms for Set Cover Leasing Problems
- Towards flexible demands in online leasing problems
- Tight approximation bounds for maximum multi-coverage
- Computational Methods in Systems Biology
- Towards the price of leasing online
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Complexity of Total {k}-Domination and Related Problems
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Tight Approximation Bounds for Maximum Multi-coverage
- Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer
- A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
- A variable neighborhood search algorithm for the multimode set covering problem
This page was built for publication: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876471)
