Approximating the online set multicover problems via randomized winnowing

DOI10.1016/j.tcs.2007.10.047zbMath1137.68061arXiv1102.4005OpenAlexW2794883302MaRDI QIDQ2481951

Piotr Berman, Bhaskar Das Gupta

Publication date: 15 April 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.4005

zbMATH Keywords

online algorithmsrandomized algorithmsset multicoverreverse engineering of biological networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Randomized algorithms (68W20) General biology and biomathematics (92B05)

Related Items (3)

Towards the price of leasing online ⋮ Randomized Online Algorithms for Set Cover Leasing Problems ⋮ Towards flexible demands in online leasing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inference of signaling and gene regulatory networks by steady-state perturbation experiments: structure and accuracy
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Approximation algorithms for combinatorial problems
• Tight approximability results for test set problems in bioinformatics
• Admission control to minimize rejections and online set cover with repetitions
• A general approach to online network optimization problems
• A threshold of ln n for approximating set cover
• The Online Set Cover Problem
• Non-approximability results for optimization problems on bounded degree instances
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Approximating the online set multicover problems via randomized winnowing