TY - JOUR
T1 - Approximating the online set multicover problems via randomized winnowing
AU - Berman, Piotr
AU - DasGupta, Bhaskar
N1 - Funding Information:
The first author was supported by NSF grant CCR-0208821. The second author was supported in part by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973.
PY - 2008/3/20
Y1 - 2008/3/20
N2 - 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 {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 leastk 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].
AB - 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 {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 leastk 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].
UR - http://www.scopus.com/inward/record.url?scp=39649102776&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=39649102776&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2007.10.047
DO - 10.1016/j.tcs.2007.10.047
M3 - Article
AN - SCOPUS:39649102776
SN - 0304-3975
VL - 393
SP - 54
EP - 71
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -