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

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

On Lower Bound of On-Line Broadcast Scheduling Problem

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.