Treffer: On-line windows scheduling of temporary items
Title:
On-line windows scheduling of temporary items
Authors:
Source:
Algorithms and computation (Hong Kong, 20-22 December 2004)Lecture notes in computer science. :259-270
Publisher Information:
Berlin: Springer, 2004.
Publication Year:
2004
Physical Description:
print, 15 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme compétitif, Competitive algorithms, Algorithmique, Algorithmics, Algorítmica, Borne inférieure, Lower bound, Cota inferior, Ordonnancement, Scheduling, Reglamento
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, University of Hong Kong, Hong-Kong
Department of Computer Science, University of Liverpool, United Kingdom
Department of Computer Science, University of Liverpool, United Kingdom
ISSN:
0302-9743
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16368785
Database:
PASCAL Archive
Weitere Informationen
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.