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

• 作者: 徐寅峰 郑斐峰
• 来源期刊: 西安交通大学学报
• 关键词: 广播调度 确定性算法 竞争比 中断比
• 年，卷（期）: 2005,（12）
• 页码范围: 1291-1294
• 页数: 4页
• 分类号: TP393
• 语种: 中文
• DOI: 10.3321/j.issn:0253-987X.2005.12.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐寅峰	西安交通大学管理学院	138	1984	23.0	37.0
2	郑斐峰	西安交通大学管理学院	21	281	8.0	16.0