In this invited talk, we present techniques and restuls from a joint work with Oliver Goebel, Martin Hoefer, Thomas Kesselheim, and Thomas Schleiden. We study 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 and spectrum allocation. In the considered online setting, it is assumed that 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. We explain that this natural and practically relevant online problem cannot be studied in a meaningful way within a classical competitive analysis as the competitive ratio on worst-case input sequences is lower bounded by Ω(n). This devastating lower bound holds even for randomized algorithms on unweighted interval graphs and, hence, for the most restricted graph class under consideration.
展开▼
