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 request ed by the clients is delivered via broadcast. In particular, we consider th e case where all the data items are of equal size and preemption is not all owed. We give an offline O(1)-speed O(1)-approximation algorithm for the pr oblem of minimizing the average response time. We provide worst-case analys is, under various objective functions, of the online algorithms that have a ppeared in the literature, namely, Most Requests First, First Come First Se rved, and Longest Wait First. Copyright (C) 2001 John Wiley & Sons, Ltd.