Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-092 | 10th July 2007 00:00

Approximating the Online Set Multicover Problems Via Randomized Winnowing


Authors: Piotr Berman, Bhaskar DasGupta
Publication: 26th September 2007 15:17
Downloads: 3433


In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of elements are presented online in an arbitrary order. When each element i_p is presented, we are also told the collection of all (at least k) sets SS_{i_p}\subseteq SS and their costs in which i_p belongs and we need to select additional sets from SS_{i_p} if necessary
such that our collection of selected sets contains at least k sets that contain the element i_p. 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 prespecified 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. This algorithm generalizes and improves some earlier results. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k.

ISSN 1433-8092 | Imprint