ECCC-Report TR07-092https://eccc.weizmann.ac.il/report/2007/092Comments and Revisions published for TR07-092en-usWed, 26 Sep 2007 15:17:44 +0200
Paper TR07-092
| Approximating the Online Set Multicover Problems Via Randomized Winnowing |
Piotr Berman,
Bhaskar DasGupta
https://eccc.weizmann.ac.il/report/2007/092In 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.
Wed, 26 Sep 2007 15:17:44 +0200https://eccc.weizmann.ac.il/report/2007/092