Randomized Online Algorithms for Set Cover Leasing Problems Abshoff, Sebastian Markarian, Christine Meyer auf der Heide, Friedhelm ddc:040 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. 2014 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://ris.uni-paderborn.de/record/379 Abshoff S, Markarian C, Meyer auf der Heide F. Randomized Online Algorithms for Set Cover Leasing Problems. In: <i>Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ; 2014:25-34. doi:<a href="https://doi.org/10.1007/978-3-319-12691-3_3">10.1007/978-3-319-12691-3_3</a> info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-12691-3_3 info:eu-repo/semantics/closedAccess