The Data Broadcast Problem with Non-Uniform Transmission Times

被引：0

作者：

机构：

[1] LRI,

[2] Université Paris XI,undefined

[3] Bâtiment 490,undefined

[4] F-91405 Orsay,undefined

[5] http://www.lri.fr/~kenyon.,undefined

[6] CNRS,undefined

[7] LIP,undefined

[8] UMR CNRS-ENS Lyon-INRIA n°5668,undefined

[9] 46 allée d'Italie,undefined

[10] F-69364 Lyon Cedex 07,undefined

[11] http://www.ens-lyon.fr/~nschaban.,undefined

来源：

Algorithmica | 2003年 / 35卷

关键词：

Approximation algorithms, Scheduling, Randomized algorithms, NP-Completeness, Data broadcasting;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：146 / 175

页数：29

共 50 条

[41] Uniform and non-uniform partitioned 64-QAM for mobile video transmission
Theodorakopoulos, Vasileios
Woodward, Michael E.
Sotiropoulou, Kaliopi
Proceedings of the Ninth IASTED International Conference on Internet and Multimedia Systems and Applications, 2005, : 418 - 423
[42] Data-Parallel Query Processing on Non-Uniform Data
Funke, Henning
Teubner, Jens
PROCEEDINGS OF THE VLDB ENDOWMENT, 2020, 13 (06): : 884 - 897
[43] THE UNIFORM SPREADING SPEED IN COOPERATIVE SYSTEMS WITH NON-UNIFORM INITIAL DATA
Hou, Ru
Wang, Zhian
Xu, Wen-Bing
Zhang, Zhitao
DISCRETE AND CONTINUOUS DYNAMICAL SYSTEMS-SERIES S, 2024, 17 (02): : 585 - 601
[44] Data Sampling and Processing: Uniform vs. Non-Uniform Schemes
Beyrouthy, Taha
Fesquet, Laurent
Rolland, Robin
PROCEEDINGS OF FIRST INTERNATIONAL CONFERENCE ON EVENT-BASED CONTROL, COMMUNICATION AND SIGNAL PROCESSING EBCCSP 2015, 2015,
[45] Dispersion compensation using transmission based non-uniform grating
Survaiya, SP
Saxena, S
OPTICAL ENGINEERING FOR SENSING AND NANOTECHNOLOGY (ICOSN 2001), 2001, 4416 : 170 - 173
[46] Validation of a modified FDTD method on non-uniform transmission lines
Trakadas, P.T.
Capsalis, C.N.
Progress in Electromagnetics Research, 2001, 31 : 311 - 329
[47] Analytic solution of non-uniform transmission lines at low frequencies
Khalaj-Amirhosseini, M.
IET MICROWAVES ANTENNAS & PROPAGATION, 2009, 3 (08) : 1218 - 1223
[48] NON-UNIFORM TRANSMISSION LINE SYNTHESIS BY LEAST SQUARES.
Oraizi, H.
Perini, J.
Iranian Journal of Science and Technology, 1976, 5 (03): : 131 - 141
[49] Secrecy and Connection Performance for Uplink Transmission in Non-Uniform HetNets
Wu, Huici
Tao, Xiaofeng
Chen, Hui
Li, Na
Xu, Jin
2016 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM), 2016,
[50] Adaptive Transmission Strategy for Non-Uniform Coding of 360° Videos
Guo, Jia
Li, Shiqiang
Zhu, Jinqi
Li, Xiang
Sun, Bowen
Feng, Weijia
ELECTRONICS, 2024, 13 (16)

← 1 2 3 4 5 →