Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
From MaRDI portal
Publication:876471
DOI10.1016/j.dam.2004.11.009zbMath1163.68045OpenAlexW2163141979MaRDI QIDQ876471
Eduardo D. Sontag, Piotr Berman, Bhaskar Das Gupta
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
Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (12)
Tight Approximation Bounds for Maximum Multi-coverage ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ Towards the price of leasing online ⋮ Randomized Online Algorithms for Set Cover Leasing Problems ⋮ A variable neighborhood search algorithm for the multimode set covering problem ⋮ Complexity of Total {k}-Domination and Related Problems ⋮ Towards flexible demands in online leasing problems ⋮ Approximating the online set multicover problems via randomized winnowing ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Tight approximation bounds for maximum multi-coverage ⋮ Randomized approximation for the set multicover problem in hypergraphs
Cites Work
- A new polynomial-time algorithm for linear programming
- Inference of signaling and gene regulatory networks by steady-state perturbation experiments: structure and accuracy
- Approximation algorithms for combinatorial problems
- A threshold of ln n for approximating set cover
- Enumeration of Seven-Argument Threshold Functions
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
