互联网 qkzz.net
全刊杂志网:首页 > 大学学报 > 文章正文
刊社推荐

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


□ 徐寅峰 郑斐峰

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

 未安装PDF浏览器用户请先下载安装
原版页码:1291,1292,1293,1294原版全文
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文
关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | EMS快递查询
全刊杂志赏析网 2016