Online Broadcast Scheduling: Minimizing the Maximum Response Time

Broadcast scheduling is a widely used mechanism for disseminating vast amounts of information. In this model, information is discretized into “pages”, which clients explicitly request. The primary advantage of broadcasting is that any number of outstanding requests may be satisfied via only one broadcast. There are several ways to measure the quality of a schedule. The majority of this paper is devoted to the study of the FIFO algorithm for online broadcasting, in which the server does not know anything about future requests at any given time, with the goal of minimizing the maximum response time. In addition, an integrality gap for throughput maximization and a few greedy approaches to the problem of broadcasting with fixed maximum response times are described.