A near optimal scheduler for on-demand data broadcasts

On-demand data broadcasting is a new and important technique for information dissemination. In this paper, we design and analyse a novel online scheduler Balance for scheduling on-demand data broadcasts. Balance has competitive ratio , which improves significantly the previous best upper bound of . We also prove that any online scheduler for the problem cannot have competitive ratio smaller than . It follows that Balance is optimal within a constant factor.