The Data Broadcast Problem with Non-Uniform Transmission Times |
| |
Authors: | Kenyon and Schabanel |
| |
Affiliation: | (1) LRI, Université Paris XI, Batiment 490, F-91405 Orsay, France. http://www.lri.fr/~kenyon., FR;(2) CNRS, LIP, UMR CNRS-ENS Lyon-INRIA n°5668, 46 allée d'Italie, F-69364 Lyon Cedex 07, France. http://www.ens-lyon.fr/~nschaban., FR |
| |
Abstract: | Abstract. 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. |
| |
Keywords: | . Approximation algorithms Scheduling Randomized algorithms NP-Completeness Data broadcasting. |
本文献已被 SpringerLink 等数据库收录! |
|