Approximating the online set multicover problems via randomized winnowing

AbstractIn 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 S∈S, and a “coverage factor” (positive integer) k. A subset {i0,i1,…}⊆V of elements are presented online in an arbitrary order. When each element ip is presented, we are also told the collection of all (at least k) sets Sip⊆S and their costs to which ip belongs and we need to select additional sets from Sip if necessary such that our collection of selected sets contains at least k sets that contain the element ip. The goal is to minimize the total cost of the selected sets.11Our 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 of [N. Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (1988) 285–318]. This algorithm generalizes and improves some earlier results in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, A general approach to online network optimization problems, in: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 570–579; N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105]. We also discuss lower bounds on competitive ratios for deterministic algorithms for general k based on the approaches in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor, The online set cover problem, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 100–105]