Approximating the online set multicover problems via randomized winnowing

摘要

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 S ∈ S, and a "coverage factor" (positive integer) k. A subset {i{sub}O, i{sub}1,...} {is contained in} V of elements are presented online in an arbitrary order. When each element i{sub}p is presented, we are also told the collection of all (at least k) sets S{sub}(i{sub}p) {is contained in}S and their costs to which i{sub}p belongs and we need to select additional sets from S{sub}(i{sub}p) if necessary such that our collection of selected sets contains at least k sets that contain the element i{sub}p. The goal is to minimize the total cost of the selected sets. 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) 28.5-318]. This algorithm generalizes and improves some earlier results in [N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, I, 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].