2026-07-22T11:41:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6414 2024-03-06T10:38:12Z ddc:004 open_access

Online Budgeted Maximum Coverage Rawitz, Dror Rosén, Adi budgeted coverage maximum coverage online algorithms competitive analysis removable online knapsack We study the Online Budgeted Maximum Coverage (OBMC) problem. Subsets of a weighted ground set U arrive one by one, where each set has a cost. The online algorithm has to select a collection of sets, under the constraint that their cost is at most a given budget. Upon arrival of a set the algorithm must decide whether to accept or to reject the arriving set, and it may also drop previously accepted sets (preemption). Rejecting or dropping a set is irrevocable. The goal is to maximize the total weight of the elements covered by the sets in the chosen collection. We present a deterministic 4/(1-r)-competitive algorithm for OBMC, where r is the maximum ratio between the cost of a set and the total budget. Building on that algorithm, we then present a randomized O(1)-competitive algorithm for OBMC. On the other hand, we show that the competitive ratio of any deterministic online algorithm is Omega(1/(sqrt{1-r})). We also give a deterministic O(Delta)-competitive algorithm, where Delta is the maximum weight of a set (given that the minimum element weight is 1), and if the total weight of all elements, w(U), is known in advance, we show that a slight modification of that algorithm is O(min{Delta,sqrt{w(U)}})-competitive. A matching lower bound of Omega(min{Delta,sqrt{w(U)}}) is also given. Previous to the present work, only the unit cost version of OBMC was studied under the online setting, giving a 4-competitive algorithm [Saha, Getoor, 2009]. Finally, our results, including the lower bounds, apply to Removable Online Knapsack which is the preemptive version of the Online Knapsack problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dror Rawitz and Adi Rosén 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.73 urn:nbn:de:0030-drops-64146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.73 eng https://creativecommons.org/licenses/by/3.0/legalcode