Randomized Online Algorithms for Set Cover Leasing Problems

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 family \(F\) of subsets of \(U\). Each set can be leased for \(K\) different periods of time. Let \(\left| U \right| = n\) and \(\left| F \right| = m\). Leasing a set \(S\) for a period \(k\) incurs a cost \(c_{S}^{k}\) and allows \(S\) to cover its elements for the next \(l_k\) time steps. The objective is to minimize the total cost of the sets leased, such that elements arriving at any time \(t\) are covered by sets which contain them and are leased during time \(t\). Anthony et al. [1] gave an optimal \(O(\log n)\)-approximation for the problem in the offline setting, unless \(\mathcal {P} = \mathcal {NP}\) [22]. In this paper, we give randomized algorithms for variants of Set Cover Leasing in the online setting, including a generalization of Online Set Cover with Repetitions presented by Alon et al. [2], where elements appear multiple times and must be covered by a different set at each arrival. Our results improve the \(\mathcal {O}(\log ^2 (mn))\) competitive factor of Online Set Cover with Repetitions [2] to \(\mathcal {O}(\log d \log (dn)) = \mathcal {O}(\log m \log (mn))\), where \(d\) is the maximum number of sets an element belongs to.