Title: Online Independent Set Beyond the Worst-Case
Abstract: We investigate online algorithms for maximum independent set on graph classes with bounded inductive independence number $\rho$ 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. Since traditional (worst-case) competitive analysis only yields devastating results, 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.