2014 | OriginalPaper | Buchkapitel
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
verfasst von : Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, Berthold Vöcking
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
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
We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number
ρ
like interval and disk graphs with applications to, e.g., task scheduling, spectrum allocation and admission control. In the online setting, nodes of an unknown graph arrive one by one over time. An online algorithm has to decide whether an arriving node should be included into the independent set.
Traditional (worst-case) competitive analysis yields only devastating results. Hence, we conduct a stochastic analysis of the problem and introduce a generic sampling approach that allows to devise online algorithms for a variety of input models. It bridges between models of quite different nature – it covers the secretary model, in which an adversarial graph is presented in random order, and the prophet-inequality model, in which a randomly generated graph is presented in adversarial order.
Our first result is an online algorithm for maximum independent set with a competitive ratio of
O
(
ρ
2
) in all considered models. It can be extended to maximum-weight independent set by losing only a factor of
O
(log
n
), with
n
denoting the (expected) number of nodes. This upper bound is complemented by a lower bound of Ω(log
n
/log
2
log
n
) showing that our sampling approach achieves nearly the optimal competitive ratio in all considered models. In addition, we present various extensions, e.g., towards admission control in wireless networks under SINR constraints.