---
res:
bibo_abstract:
- In the leasing variant of Set Cover presented by Anthony et al.[1], elements U
arrive over time and must be covered by sets from a familyF of subsets of U. Each
set can be leased for K different periods of time.Let |U| = n and |F| = m. Leasing
a set S for a period k incurs a cost ckS and allows S to cover its elements for
the next lk time steps. The objectiveis to minimize the total cost of the sets
leased, such that elements arrivingat any time t are covered by sets which contain
them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log n)-approximation
forthe problem in the offline setting, unless P = NP [22]. In this paper, wegive
randomized algorithms for variants of Set Cover Leasing in the onlinesetting,
including a generalization of Online Set Cover with Repetitionspresented by Alon
et al. [2], where elements appear multiple times andmust be covered by a different
set at each arrival. Our results improve theO(log2(mn)) competitive factor of
Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)), where
d is the maximum numberof sets an element belongs to.
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sebastian
foaf_name: Abshoff, Sebastian
foaf_surname: Abshoff
- foaf_Person:
foaf_givenName: Christine
foaf_name: Markarian, Christine
foaf_surname: Markarian
foaf_workInfoHomepage: http://www.librecat.org/personId=37612
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
bibo_doi: 10.1007/978-3-319-12691-3_3
dct_date: 2014^xs_gYear
dct_title: Randomized Online Algorithms for Set Cover Leasing Problems@
...