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.