Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Randomized Online Algorithms for Set Cover Leasing Problems
verfasst von : Sebastian Abshoff, Christine Markarian, Friedhelm Meyer auf der Heide
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.