The data broadcast problem with non-uniform transmission times

Abstract

. The data broadcast problem consists in finding an infinite schedule to broadcast a given set of messages so as to minimize the average response time to clients requesting messages, and 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 the more realistic setting of continuous time and messages of non-uniform transmission times. The structural properties of the optimal solutions appear to be very di#erent from the uniform case. We prove that the data broadcast problem is NP-hard, even if the broadcast costs are all zero, and give a randomized 3-approximation algorithm for broadcasting messages on a single channel. 1 Introduction 1.1 Motivation This paper studies an optimization problem which arises in three contexts: Data broadcasting, Scheduling ma...