Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
复制标题
超越最坏情况的在线独立集：秘书、先知和时期
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Berthold Vöcking
中科院分区：
文献类型：
--
作者：
O. Göbel;M. Hoefer;Thomas Kesselheim;T. Schleiden;Berthold Vöcking
我们在线研究最大（权重）独立设置的图形类别具有有界的归纳独立数ρ，例如间隔和磁盘图，并在线设置中的应用程序调度，频谱分配和录取控制。随着时间的推移，一个在线算法必须确定是否应将到达节点包含在独立集中。
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.