On Broadcast Scheduling with Limited Energy

摘要

Given a set of requests, we tackle the problem of finding 'good' broadcast schedules aiming at the minimization of their total flow time. While running at a fixed speed, in the considered model the server is only allowed to use a certain amount of energy to perform these broadcasts. For this task we present optimal and approximation algorithms, respectively, depending on the number of distinct request types and their transmission lengths. The problem is solvable within polynomial time in the offline setting if the transmission lengths of all request types are identical and the number of distinct request types is constant. The presented algorithm can be generalized to obtain an approximation on instances without identical transmission lengths. Regarding the online version, we show lower and upper bounds on the competitive ratio of an optimal algorithm, including randomized algorithms and algorithms using resource augmentation. These lower and corresponding upper bounds match (at least asymptotically).