More Web Proxy on the site http://driver.im/

Article

Windows scheduling problems for broadcast systems

Authors:

Richard E. LadnerAuthors Info & Claims

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 433 - 442

Published: 06 January 2002 Publication History

Abstract

The windows scheduling problem is defined by the positive integers h and w₁, w₂,…, w_n. The window w_i is associated with page i and h is the number of slotted channels available for broadcasting the pages. A schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most w_i slots. We investigate two optimization problems. (i) The optimal windows scheduling problem: given w₁,…, w_n find a schedule in which h is minimized. (ii) The optimal harmonic windows scheduling problem: given h find a schedule for the windows w_i = i in which n is maximized. The former is a formulation of the problem of minimizing the bandwidth in push systems that support guaranteed delay and the latter is a formulation of the problem of minimizing the startup delay in media-on-demand systems. For the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules and for the optimal harmonic windows scheduling problem, we show how to achieve the largest known n's for all values of h.

References

[1]

S. Acharya, M. J. Franklin, and S. Zdonik. Dissemination-based Data Delivery Using Broadcast Disks. IEEE Personal Communications, Vol. 2(6), 50-60, 1995.

[2]

M. H. Ammar and J. W. Wong. The Design of Teletext broadcast cycles. Performance Evaluation, Vol. 5(4), 235-242, 1985.

[3]

A. Bar-Noy, R. Bhatia, J. Naor, and B. Schieber. Minimizing service and operation costs of periodic scheduling. In Proceedings of the 9-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '98), 11-20, 1998.

Digital Library

[4]

A. Bar-Noy, J. Naor, and B. Schieber. Pushing Dependent Data in Clients-Providers-Servers Systems. In Proceedings of the 6-th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), 222-230, 2000.

Digital Library

[5]

A. Bar-Noy, A. Nisgav, and B. Patt-Shamir. Nearly Optimal Perfectly-Periodic Schedules. In Proceedings of the 20-th ACM Symposium on Principles of Distributed Computing (PODC '01), 107-116, 2001.

Digital Library

[6]

L. Engebretsen and M. Sudan. Harmonic broadcasting is optimal In Proceedings of the 13-th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), 2002.

Digital Library

[7]

V. Gondhalekar, R. Jain, and J. Werth. Scheduling on airdisks: efficient access to personalized information services via periodic wireless data broadcast. University of Texas at Austin, Technical Report TR-96-25.

Digital Library

[8]

K. A. Hua, Y. Cai, and S. Sheu Exploiting client bandwidth for more efficient video broadcast. In Proceedings of the 7-th International Conference on Computer Communication and Networks (ICCCN '98), 848-856, 1998.

Digital Library

[9]

K. A. Hua and S. Sheu. Skyscraper broadcasting: a new broadcasting scheme for metropolitan video-on-demand systems. In Proceedings of the ACM SIGCOMM '97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 89-100, 1997.

Digital Library

[10]

L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Transactions on Broadcasting, Vol. 43, No. 3, 268-271, 1997.

[11]

L. Juhn and L. Tseng. Fast data broadcasting and receiving scheme for popular video service. IEEE Transactions on Broadcasting, Vol. 44, No. 1, 100-105, 1998.

[12]

J. Pâris. A simple low-bandwidth broadcasting protocol for video-on-demand. In Proceedings of the 8-th International Conference on Computer Communications and Networks (IC3N '99), 118-123, 1999.

[13]

J. Pâris, S. W. Carter, and D. D. E. Long. A low bandwidth broadcasting protocol for video on demand. In Proceedings of the 7-th International Conference on Computer Communications and Networks (IC3N '98), 690-697, 1998.

Digital Library

[14]

J. Pâris, S. W. Carter, and D. D. E. Long. A hybrid broadcasting protocol for video on demand. In Proceedings of the IS&T/SPIE Conference on Multimedia Computing and Networking (MMCN '99), 317-326, 1999.

[15]

S. Viswanathan and T. Imielinski. Metropolitan area video-on-demand service using pyramid broadcasting. ACM Multimedia Systems Journal, Vol. 4(3), 197-208, 1996.

Digital Library

[16]

S. Wolfram. Mathematica a System for Doing Mathematics by Computers. Addison-Wesley Publishing.

Digital Library

Cited By

Sun YMa FKameda T(2009)Generating asymptotically optimal broadcasting schedules to minimize average waiting timeDiscrete Mathematics10.1016/j.disc.2008.05.025309:18(5714-5723)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.disc.2008.05.025
Kameda TSun YGoddyn L(2005)An optimization problem related to vod broadcastingProceedings of the 16th international conference on Algorithms and Computation10.1007/11602613_13(116-125)Online publication date: 19-Dec-2005
https://dl.acm.org/doi/10.1007/11602613_13
Sgall JShachnai HTamir T(2005)Fairness-free periodic scheduling with vacationsProceedings of the 13th annual European conference on Algorithms10.1007/11561071_53(592-603)Online publication date: 3-Oct-2005
https://dl.acm.org/doi/10.1007/11561071_53
Show More Cited By

Windows scheduling problems for broadcast systems
1. Networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Windows Scheduling Problems for Broadcast Systems

The windows scheduling problem is defined by the positive integers n, h, and w₁, ...,w_n. There are n pages where the window w_i is associated with page i, and h is the number of slotted channels available for broadcasting the pages. A schedule that ...
Single machine scheduling problems with deteriorating jobs

This paper considers the single machine scheduling problems with deteriorating jobs, i.e. jobs whose processing times are a decreasing linear function of their starting time. It is assumed that jobs have the different basic processing time and same ...
Approximation schemes for constrained scheduling problems
SFCS '89: Proceedings of the 30th Annual Symposium on Foundations of Computer Science

Several constrained scheduling problems are considered. The first polynomial approximation schemes for the problem of minimizing maximum completion time in a two-machine flow shop with release dates and for the problem of minimizing maximum lateness for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

January 2002

1018 pages

ISBN:089871513X

Conference Chair:
David Eppstein

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2002

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
325
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun YMa FKameda T(2009)Generating asymptotically optimal broadcasting schedules to minimize average waiting timeDiscrete Mathematics10.1016/j.disc.2008.05.025309:18(5714-5723)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.disc.2008.05.025
Kameda TSun YGoddyn L(2005)An optimization problem related to vod broadcastingProceedings of the 16th international conference on Algorithms and Computation10.1007/11602613_13(116-125)Online publication date: 19-Dec-2005
https://dl.acm.org/doi/10.1007/11602613_13
Sgall JShachnai HTamir T(2005)Fairness-free periodic scheduling with vacationsProceedings of the 13th annual European conference on Algorithms10.1007/11561071_53(592-603)Online publication date: 3-Oct-2005
https://dl.acm.org/doi/10.1007/11561071_53
Sun YKameda T(2005)Harmonic block windows scheduling through harmonic windows schedulingProceedings of the 11th international conference on Advances in Multimedia Information Systems10.1007/11551898_17(190-206)Online publication date: 19-Sep-2005
https://dl.acm.org/doi/10.1007/11551898_17
Bar-Noy ALadner RTamir TMunro I(2004)Windows scheduling as a restricted version of Bin PackingProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982824(224-233)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982824
Bar-Noy ALadner RTamir T(2003)Scheduling techniques for media-on-demandProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644238(791-800)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644238

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents