Abstract
We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479–488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). In the case that pages may have different lengths, we give a ( \(\Delta+ 2\sqrt{\Delta}+2\) )-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). We also prove an almost matching lower bound of Ω(Δ/log Δ). Furthermore, for small values of Δ we give better lower bounds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aksoy, D., & Franklin, M. (1998). Scheduling for large scale on-demand data broadcast. In Proceedings of IEEE INFOCOM (pp. 651–659).
Bartal, Y., & Muthukrishnan, S. (2000). Minimizing maximum response time in scheduling broadcasts. In Proceedings 11th ACM–SIAM symposium on discrete algorithms (pp. 558–559).
Borodin, A., & El-yaniv, R. (1998). Online computation and competitive analysis. Cambridge: Cambridge University Press.
Chan, W.-T., Lam, T.-W., Ting, H.-F., & Wong, P. W. H. (2004). New results on on-demand broadcasting with deadline via job scheduling with cancellation. In Lecture notes in computer science : Vol. 3106. 10th international computing and combinatorics conference (pp. 210–218). Berlin: Springer.
DirecPC Home Page. http://www.direcpc.com/
Edmonds, J., & Pruhs, K. (2002). Broadcast scheduling: when fairness is fine. In Proceedings 13th ACM–SIAM symposium on discrete algorithms (pp. 421–430).
Erlebach, T., & Hall, A. (2002). NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. In Proceedings 13th ACM–SIAM symposium on discrete algorithms (pp. 194–202).
Gandhi, R., Khuller, S., Kim, Y. A., & Wan, Y. C. (2004). Algorithms for minimizing response time in broadcast scheduling. Algorithmica, 38(4), 597–608.
Jiang, S., & Vaidya, N. (1999). Scheduling data broadcasts to “impatient” users. In Proceedings ACM international workshop on data engineering for wireless and mobile access (pp. 52–59).
Kalyanasundaram, B., Pruhs, K., & Velauthapillai, M. (2000). Scheduling broadcasts in wireless networks. In Lecture notes in computer science : Vol. 1879. Proceedings 8th European symposium on algorithms (pp. 290–301). Berlin: Springer.
Kalyanasundaram, B., & Velauthapillai, M. (2003). On-demand broadcasting under deadline. In Lecture notes in computer science : Vol. 2832. Proc. 11th European symposium on algorithms (pp. 313–324). Berlin: Springer.
Kim, J.-H., & Chwa, K.-Y. (2004). Scheduling broadcasts with deadlines. Theoretical Computer Science, 325(3), 479–488.
Woeginger, G. J. (1994). On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130, 5–16.
Zheng, F., Chin, F. Y. L., Fung, S. P. Y., Poon, Ch. K., & Xu, Y. (2006). A tight lower bound for job scheduling with cancellation. Information Processing Letters, 97(1), 1–3.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G].
Rights and permissions
About this article
Cite this article
Fung, S.P.Y., Zheng, F., Chan, WT. et al. Improved on-line broadcast scheduling with deadlines. J Sched 11, 299–308 (2008). https://doi.org/10.1007/s10951-007-0036-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-007-0036-6