License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.73
URN: urn:nbn:de:0030-drops-64146
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6414/
Go to the corresponding LIPIcs Volume Portal

Rawitz, Dror ; Rosén, Adi

Online Budgeted Maximum Coverage

pdf-format:
LIPIcs-ESA-2016-73.pdf (0.5 MB)

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/(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.

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:1--73:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6414},
  URN =		{urn:nbn:de:0030-drops-64146},
  doi =		{10.4230/LIPIcs.ESA.2016.73},
  annote =	{Keywords: budgeted coverage, maximum coverage, online algorithms, competitive analysis,  removable online knapsack}
}

Keywords: budgeted coverage, maximum coverage, online algorithms, competitive analysis, removable online knapsack
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI