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 条

[1] The data broadcast problem with non-uniform transmission times
Kenyon, C
Schabanel, N
PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1999, : 547 - 556
[2] The data broadcast problem with non-uniform transmission times
Kenyon, C
Schabanel, N
ALGORITHMICA, 2003, 35 (02) : 146 - 175
[3] A Non-uniform Bound on Matching Problem
Teerapabolarn, Kanint
Neammanee, Kritsana
KYUNGPOOK MATHEMATICAL JOURNAL, 2006, 46 (04): : 489 - 496
[4] Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times
Lau, Haye
Huang, Shoudong
Dissanayake, Gamini
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 190 (02) : 383 - 397
[5] Evaluation of Non-Uniform Constellations for the Converged Network of Broadcast and Broadband
Hong, Hanjiang
Xu, Yin
He, Dazhi
Gao, Na
Wu, Yiyan
Zhang, Wenjun
2019 IEEE INTERNATIONAL SYMPOSIUM ON BROADBAND MULTIMEDIA SYSTEMS AND BROADCASTING (BMSB), 2019,
[6] Spatial query processing for skewed access patterns in non-uniform wireless data broadcast environments
Shen, Jun-Hong
Jian, Ming-Shen
INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING, 2017, 25 (1-2) : 4 - 16
[7] TRANSFORMATIONS IN ANALYSIS OF NON-UNIFORM TRANSMISSION LINES
SCHWARTZ, RF
JOURNAL OF THE FRANKLIN INSTITUTE-ENGINEERING AND APPLIED MATHEMATICS, 1964, 278 (03): : 163 - &
[8] A New Model for Non-uniform Transmission Lines
Martinez, David
Moreno, Pablo
Loo-Yau, Raul
2015 12TH INTERNATIONAL CONFERENCE ON ELECTRICAL ENGINEERING, COMPUTING SCIENCE AND AUTOMATIC CONTROL (CCE 2015), 2015,
[9] NON-UNIFORM TRANSMISSION LINES AND REFLECTION COEFFICIENTS
WALKER, LR
WAX, N
JOURNAL OF APPLIED PHYSICS, 1946, 17 (12) : 1043 - 1045
[10] Gears and Belt Drives for Non-Uniform Transmission
Stachel, Hellmuth
PROCEEDINGS OF EUCOMES 08, THE SECOND EUROPEAN CONFERENCE ON MECHANISM SCIENCE, 2009, : 415 - 422

← 1 2 3 4 5 →