Polynomial-Time Approximation Scheme for Data Broadcast

Details Polynomial-Time Approximation Scheme for Data Broadcast Polynomial-Time Approximation Scheme for Data Broadcast

2002-05-10

arxiv.org/abs/cs/0205012v1

ACM Symposium on Theory of Computing (2000)

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Polynomial-Time Approximation Scheme for Data Broadcast does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial-Time Approximation Scheme for Data Broadcast, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial-Time Approximation Scheme for Data Broadcast will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-382486