Approximating the online set multicover problems via randomized winnowing

DOI10.1016/J.TCS.2007.10.047MaRDI QIDQ2481951zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Bhaskar Dasgupta

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) Randomized algorithms (68W20) Approximation algorithms (68W25) General biology and biomathematics (92B05)

Abstract: In this paper, we consider the weighted online set k-multicover problem. In this problem, we have a universe V of elements, a family S of subsets of V with a positive real cost for every set in S and a "coverage factor" (positive integer) k. A subset of elements are presented online in an arbitrary order. When each element, say i, is presented, we are also told the collection of all (at least k) sets and their costs to which i belongs and we need to select additional sets from these sets containing i, if necessary, such that our collection of selected sets contains at least k sets that contain the element i. The goal is to minimize the total cost of the selected sets (our algorithm and competitive ratio bounds can be extended to the case when a set can be selected at most a pre-specified number of times instead of just once; we do not report these extensions for simplicity and also because they have no relevance to the biological applications that motivated our work). In this paper, we describe a new randomized algorithm for the online multicover problem based on a randomized version of the winnowing approach of Littlestone. This algorithm generalizes and improves some earlier results by N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. We also discuss lower bounds on competitive ratios for deterministic algorithms for general $k$.

Recommendations

• Algorithms and Data Structures
• A primal-dual randomized algorithm for the online weighted set multi-cover problem
• Randomized online algorithms for set cover leasing problems
• Online and dynamic algorithms for set cover
• The online set cover problem
• The online set cover problem
• Improved analysis of the online set cover problem with advice
• The Online Submodular Cover Problem
• Approximation algorithm for the stochastic prize-collecting set multicover problem
• Randomized approximation for the set multicover problem in hypergraphs

Cites work

• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 1256771 (Why is no real title available?)
• scientific article; zbMATH DE number 1263202 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A general approach to online network optimization problems
• A threshold of ln n for approximating set cover
• Admission control to minimize rejections and online set cover with repetitions
• Approximation algorithms for combinatorial problems
• Inference of signaling and gene regulatory networks by steady-state perturbation experiments: structure and accuracy
• Non-approximability results for optimization problems on bounded degree instances
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• The online set cover problem
• Tight approximability results for test set problems in bioinformatics

Cited in

(8)

• The online set cover problem
• Randomized online algorithms for set cover leasing problems
• The online set cover problem
• Admission control to minimize rejections and online set cover with repetitions
• Towards flexible demands in online leasing problems
• Towards the price of leasing online
• Online set multicover algorithms for dynamic D2D communications
• Algorithms and Data Structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481951)