徐寅峰，郑斐峰
（西安交通大学管理学院，710049,西安）
摘要:通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59，来剖析所有请求均为紧时限的特殊情形，并运用最坏情形分析法分析得出，在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征，进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出，当请求均为紧时限时，竞争比下界为4.由于紧时限是任意时限的一个特例，从而得出请求为任意时限时的竞争比下界至少为4的结论.
关键词:广播调度；确定性算法；竞争比；中断比
中图分类号:TP393文献标识码:A文章编号:0253-987X(2005)12-1291-04