10.1007/978-3-319-12691-3_3
Abshoff, Sebastian
Sebastian
Abshoff
Markarian, Christine
Christine
Markarian
Meyer auf der Heide, Friedhelm
Friedhelm
Meyer auf der Heide
Randomized Online Algorithms for Set Cover Leasing Problems
2014
2017-10-17T12:42:06Z
2019-01-03T13:14:58Z
conference
https://ris.uni-paderborn.de/record/379
https://ris.uni-paderborn.de/record/379.json
214299 bytes
application/pdf
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.