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