The Data Broadcast Problem with Non‐Uniform Transmission Times

The Data Broadcast Problem consists of finding an infinite schedule to broadcast a given set of messages so as to minimize a linear combination of the average service time to clients requesting messages, and of the cost of the broadcast. This problem also models the Maintenance Scheduling Problem and the Multi‐Item Replenishment Problem. Previous work concentrated on a discrete‐time restriction where all messages have transmission time equal to 1. Here, we study a generalization of the model to a setting of continuous time and messages of non‐uniform transmission times. We prove that the Data Broadcast Problem is strongly NP ‐hard, even if the broadcast costs are all zero, and give 3‐approximation algorithms.