首页 | 本学科首页   官方微博 | 高级检索  
     检索      

关于占线广播调度问题的一个下界
引用本文:徐寅峰,郑斐峰.关于占线广播调度问题的一个下界[J].西安交通大学学报,2005,39(12):1291-1294.
作者姓名:徐寅峰  郑斐峰
作者单位:西安交通大学管理学院,710049,西安
基金项目:国家自然科学基金资助项目(10371094,70471035)
摘    要:通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59,来剖析所有请求均为紧时限的特殊情形,并运用最坏情形分析法分析得出,在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征,进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出,当请求均为紧时限时,竞争比下界为4.由于紧时限是任意时限的一个特例,从而得出请求为任意时限时的竞争比下界至少为4的结论.

关 键 词:广播调度  确定性算法  竞争比  中断比
文章编号:0253-987X(2005)12-1291-04
收稿时间:03 9 2005 12:00AM
修稿时间:2005年3月9日

On Lower Bound of On-Line Broadcast Scheduling Problem
Xu Yinfeng,Zheng Feifeng.On Lower Bound of On-Line Broadcast Scheduling Problem[J].Journal of Xi'an Jiaotong University,2005,39(12):1291-1294.
Authors:Xu Yinfeng  Zheng Feifeng
Abstract:Through studying of on-line broadcast scheduling problem with deadlines and with competitive ratio and its lower bound to be 5 and 2.59 by greedy and deterministic algorithm respectively,a special case that all requests have tight deadlines was analyzed.By analyzing the worst case,it was obtained that the sequence of maximal abortion ratio has traits which are decreasing gradually in a continuous abortion sequence.Then it is shown that there is no deterministic algorithm,in which the competitive ratio is less than 4 in all possible two kinds of abortion sequences.Hence it is concluded that for the special case above the lower bound of competitive ratio is 4,and it leads to that for general case of arbitrary deadline the lower bound of competitive ratio is at least 4.
Keywords:broadcast scheduling  deterministic algorithm  competitive ratio  abortion ratio
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号