File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Laxity helps in broadcast scheduling

TitleLaxity helps in broadcast scheduling
Authors
Fung, SPYChin, FYLPoon, CK
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3701 LNCS, p. 251-264 How to Cite?
DOI: http://dx.doi.org/10.1007/11560586_21
AbstractWe study the effect of laxity, or slack time, on the online scheduling of broadcasts with deadlines. The laxity of a request is defined to be the ratio between its span (difference between release time and deadline) and its processing time. All requests have a minimum guaranteed laxity. We give different algorithms and lower bounds on the competitive ratio for different ranges of values of laxity, which not only represents a tradeoff between the laxity and the competitive ratio of the system, but also bridges between interval scheduling and job scheduling techniques and results. We also give an improved algorithm for general instances in the case when requests can have different processing times. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/93121
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorPoon, CKen_HK
dc.date.accessioned2010-09-25T14:51:32Z-
dc.date.available2010-09-25T14:51:32Z-
dc.date.issued2005en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2005, v. 3701 LNCS, p. 251-264en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93121-
dc.description.abstractWe study the effect of laxity, or slack time, on the online scheduling of broadcasts with deadlines. The laxity of a request is defined to be the ratio between its span (difference between release time and deadline) and its processing time. All requests have a minimum guaranteed laxity. We give different algorithms and lower bounds on the competitive ratio for different ranges of values of laxity, which not only represents a tradeoff between the laxity and the competitive ratio of the system, but also bridges between interval scheduling and job scheduling techniques and results. We also give an improved algorithm for general instances in the case when requests can have different processing times. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleLaxity helps in broadcast schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/11560586_21-
dc.identifier.scopuseid_2-s2.0-33646176582en_HK
dc.identifier.hkuros117587en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33646176582&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3701 LNCSen_HK
dc.identifier.spage251en_HK
dc.identifier.epage264en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridPoon, CK=7202673523en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats