Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR07-092 | 10th July 2007 00:00

#### Approximating the Online Set Multicover Problems Via Randomized Winnowing

TR07-092
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