关于占线广播调度问题的一个下界

摘要：

通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59,来剖析所有请求均为紧时限的特殊情形,并运用最坏情形分析法分析得出,在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征,进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出,当请求均为紧时限时,竞争比下界为4.由于紧时限是任意时限的一个特例,从而得出请求为任意时限时的竞争比下界至少为4的结论.

关键词：广播调度、确定性算法、竞争比、中断比

所属期刊栏目：39

分类号：TP393(计算技术、计算机技术)

资助基金：中国科学院资助项目10371094;70471035

在线出版日期：2006-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1291-1294