Polynomial-Time Approximation Scheme for Data Broadcast
Claire Kenyon, Nicolas Schabanel, Neal Young · 2000
The data broadcast problem is to find a schedule for broad-casting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the expected response time to clients who periodically and probabilistically tune in to wait for particular messages. The problem models disseminating data to clients in asymmetric communication environments, where there is a much larger capacity from the information source to the clients than in the reverse direction. Examples include satellites, cable TV, internet broadcast, and mobile phones. Such en-vironments favor the "push-based" model where the server broadcasts (pushes) its information on the communication medium and multiple clients simultaneously retrieve the spe-cific information of individual interest. This sort of environment motivates the study of "broadcast disks" in Information Systems [1; 7]. In this paper we present the first polynomial-time approximation scheme for the data broadcast problem for the case when W = O(1) and each message has arbitrary probability, unit length and bounded cost. The best previous polynomial-time approximation algorithm for this case has a performance ratio of 9/8 [6].