Rawitz, Dror ;
Rosén, Adi
Online Budgeted Maximum Coverage
Abstract
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/(1r)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{1r})).
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 4competitive 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.
BibTeX  Entry
@InProceedings{rawitz_et_al:LIPIcs:2016:6414,
author = {Dror Rawitz and Adi Ros{\'e}n},
title = {{Online Budgeted Maximum Coverage}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {73:173:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6414},
URN = {urn:nbn:de:0030drops64146},
doi = {10.4230/LIPIcs.ESA.2016.73},
annote = {Keywords: budgeted coverage, maximum coverage, online algorithms, competitive analysis, removable online knapsack}
}
18.08.2016
Keywords: 

budgeted coverage, maximum coverage, online algorithms, competitive analysis, removable online knapsack 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

18.08.2016 