  The data broadcast problem is to find a schedule for broadcasting 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 environments favor the
``push-based'' model where the server broadcasts (pushes) its information on
the communication medium and multiple clients simultaneously retrieve the
specific information of individual interest.
  This paper presents the first polynomial-time approximation scheme (PTAS) for
data broadcast with O(1) channels and when 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.
