Advertisement
Published in:
2014 | OriginalPaper | Chapter
Randomized Online Algorithms for Set Cover Leasing Problems
Authors : Sebastian Abshoff, Christine Markarian, Friedhelm Meyer auf der Heide
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 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.