On-line windows scheduling of temporary items

Wun Tat Chan; Prudence W.H. Wong

doi:10.1007/978-3-540-30551-4_24

On-line windows scheduling of temporary items

Wun Tat Chan^*
, Prudence W.H. Wong

^*Corresponding author for this work

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

13 Citations (Scopus)

Abstract

In this paper we study on-line windows scheduling (WS) of temporary items. In a broadcasting system, there are some broadcast channels, each can broadcast one item in one time unit. Upon the arrival of an item with a window w, where w is a positive integer, the item has to be scheduled on a channel such that it will be broadcasted in the channel at least once every w time units until its departure. With the on-line input of these temporary items, the problem is to minimize the maximum number of channels used over all time. We give a 5-competitive on-line algorithm and show that there is a lower bound of 2 - ε for any ε > 0 on the competitive ratio of any on-line algorithm.

Original language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings
Editors	Rudolf Fleischer, Gerhard Trippen
Place of Publication	Heidelberg
Publisher	Springer Berlin Heidelberg
Pages	259-270
Number of pages	12
ISBN (Electronic)	9783540305514
ISBN (Print)	9783540241317
DOIs	https://doi.org/10.1007/978-3-540-30551-4_24
Publication status	Published - 3 Dec 2004
Event	15th International Symposium on Algorithms and Computation - , Hong Kong, China Duration: 20 Dec 2004 → 22 Dec 2004 https://link.springer.com/book/10.1007/b104582 (Link to publisher record)

Publication series

Name	Lecture Notes in Computer Science
Volume	3341
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	International Symposium on Algorithms and Computation

Conference

Conference	15th International Symposium on Algorithms and Computation
Abbreviated title	ISAAC 2004
Country/Territory	Hong Kong, China
Period	20/12/04 → 22/12/04
Internet address	https://link.springer.com/book/10.1007/b104582 (Link to publisher record)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Access to Document

10.1007/978-3-540-30551-4_24

Cite this

Chan, W. T., & Wong, P. W. H. (2004). On-line windows scheduling of temporary items. In R. Fleischer, & G. Trippen (Eds.), Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings (pp. 259-270). (Lecture Notes in Computer Science; Vol. 3341), (International Symposium on Algorithms and Computation). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-30551-4_24

Chan, Wun Tat ; Wong, Prudence W.H. / On-line windows scheduling of temporary items. Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. editor / Rudolf Fleischer ; Gerhard Trippen. Heidelberg : Springer Berlin Heidelberg, 2004. pp. 259-270 (Lecture Notes in Computer Science). (International Symposium on Algorithms and Computation).

@inproceedings{f970061593b44f85a22941a78d667d70,

title = "On-line windows scheduling of temporary items",

abstract = "In this paper we study on-line windows scheduling (WS) of temporary items. In a broadcasting system, there are some broadcast channels, each can broadcast one item in one time unit. Upon the arrival of an item with a window w, where w is a positive integer, the item has to be scheduled on a channel such that it will be broadcasted in the channel at least once every w time units until its departure. With the on-line input of these temporary items, the problem is to minimize the maximum number of channels used over all time. We give a 5-competitive on-line algorithm and show that there is a lower bound of 2 - ε for any ε > 0 on the competitive ratio of any on-line algorithm.",

author = "Chan, \{Wun Tat\} and Wong, \{Prudence W.H.\}",

note = "This research was supported in part by Hong Kong RGC Grant HKU-5172/03E. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2004; 15th International Symposium on Algorithms and Computation, ISAAC 2004 ; Conference date: 20-12-2004 Through 22-12-2004",

year = "2004",

month = dec,

day = "3",

doi = "10.1007/978-3-540-30551-4\_24",

language = "English",

isbn = "9783540241317",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "259--270",

editor = "Rudolf Fleischer and Gerhard Trippen",

booktitle = "Algorithms and Computation",

url = "https://link.springer.com/book/10.1007/b104582",

}

Chan, WT & Wong, PWH 2004, On-line windows scheduling of temporary items. in R Fleischer & G Trippen (eds), Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3341, International Symposium on Algorithms and Computation, Springer Berlin Heidelberg, Heidelberg, pp. 259-270, 15th International Symposium on Algorithms and Computation, Hong Kong, China, 20/12/04. https://doi.org/10.1007/978-3-540-30551-4_24

On-line windows scheduling of temporary items. / Chan, Wun Tat; Wong, Prudence W.H.
Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. ed. / Rudolf Fleischer; Gerhard Trippen. Heidelberg: Springer Berlin Heidelberg, 2004. p. 259-270 (Lecture Notes in Computer Science; Vol. 3341), (International Symposium on Algorithms and Computation).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - On-line windows scheduling of temporary items

AU - Chan, Wun Tat

AU - Wong, Prudence W.H.

N1 - This research was supported in part by Hong Kong RGC Grant HKU-5172/03E. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2004

PY - 2004/12/3

Y1 - 2004/12/3

N2 - In this paper we study on-line windows scheduling (WS) of temporary items. In a broadcasting system, there are some broadcast channels, each can broadcast one item in one time unit. Upon the arrival of an item with a window w, where w is a positive integer, the item has to be scheduled on a channel such that it will be broadcasted in the channel at least once every w time units until its departure. With the on-line input of these temporary items, the problem is to minimize the maximum number of channels used over all time. We give a 5-competitive on-line algorithm and show that there is a lower bound of 2 - ε for any ε > 0 on the competitive ratio of any on-line algorithm.

AB - In this paper we study on-line windows scheduling (WS) of temporary items. In a broadcasting system, there are some broadcast channels, each can broadcast one item in one time unit. Upon the arrival of an item with a window w, where w is a positive integer, the item has to be scheduled on a channel such that it will be broadcasted in the channel at least once every w time units until its departure. With the on-line input of these temporary items, the problem is to minimize the maximum number of channels used over all time. We give a 5-competitive on-line algorithm and show that there is a lower bound of 2 - ε for any ε > 0 on the competitive ratio of any on-line algorithm.

UR - https://www.scopus.com/pages/publications/35048819039

UR - https://link.springer.com/chapter/10.1007/978-3-540-30551-4_24

U2 - 10.1007/978-3-540-30551-4_24

DO - 10.1007/978-3-540-30551-4_24

M3 - Conference proceeding

AN - SCOPUS:35048819039

SN - 9783540241317

T3 - Lecture Notes in Computer Science

SP - 259

EP - 270

BT - Algorithms and Computation

A2 - Fleischer, Rudolf

A2 - Trippen, Gerhard

PB - Springer Berlin Heidelberg

CY - Heidelberg

T2 - 15th International Symposium on Algorithms and Computation

Y2 - 20 December 2004 through 22 December 2004

ER -

Chan WT, Wong PWH. On-line windows scheduling of temporary items. In Fleischer R, Trippen G, editors, Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings. Heidelberg: Springer Berlin Heidelberg. 2004. p. 259-270. (Lecture Notes in Computer Science). (International Symposium on Algorithms and Computation). doi: 10.1007/978-3-540-30551-4_24

On-line windows scheduling of temporary items

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this