Abstract

We will study a problem that arises in pull-based data dissemination systems, where information requested by clients is delivered via a broadcast channel. Client requests arrive over time. Broadcasting can exploit overlap among the client requests to reduce load. Thus, if multiple clients make a request for the same data then the server can satisfy the requests in one broadcast. We consider the off-line broadcast scheduling problem in which the client requests at different times are known in advance and our goal is to schedule the broadcasts so as to minimize the total response time.
This problem is NP-hard. We present approximation algorithms for this problems.
This is joint work with S. Khuller, Y. Kim, S. Parthasarathy, A. Srinivasan, and Y. C. Wan.