Polynomial-time approximation scheme for data broadcast
- 1 May 2000
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 659-666
- https://doi.org/10.1145/335305.335398
Abstract
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/8Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Optimal broadcasting of two files over an asymmetric channelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- On indexed data broadcastPublished by Association for Computing Machinery (ACM) ,1998
- On broadcast disk pagingPublished by Association for Computing Machinery (ACM) ,1998
- Log-time algorithms for scheduling single and multiple channel data broadcastPublished by Association for Computing Machinery (ACM) ,1997
- Energy efficient indexing on airPublished by Association for Computing Machinery (ACM) ,1994
- Schedulers for larger classes of pinwheel instancesAlgorithmica, 1993
- Response Time in a Teletext System: An Individual User's PerspectiveIEEE Transactions on Communications, 1987
- Packet delay under the golden ratio weighted TDM policy in a multiple-access channelIEEE Transactions on Information Theory, 1987
- The design of teletext broadcast cyclesPerformance Evaluation, 1985