Scheduling broadcasts in wireless networks

We consider problems involving how to schedule broadcasts in a pulled-based data-dissemination service, such as the DirecPC system, where data requested by the clients are delivered via broadcast. In particular, we consider the case where all the data items are of equal size and preemption is not allowed. We give an offline O(1)-speed O(1)-approximation algorithm for the problem of minimizing the average response time. We provide worst-case analysis, under various objective functions, of the online algorithms that have appeared in the literature, namely, Most Requests First, First Come First Served, and Longest Wait First.