File Download
Supplementary

Conference Paper: Nonclairvoyant speed scaling for flow and energy

TitleNonclairvoyant speed scaling for flow and energy
Authors
Chan, HLEdmonds, JLam, TWLee, LKMarchetti-Spaccamela, APruhs, K
Issue Date2009
PublisherIBFI Schloss Dagstuhl.
Citation
The 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), University of Freiburg, Freiburg, Germany, 26-28 February 2009. In Conference Proceedings, 2009, p. 225-264 How to Cite?
AbstractWe study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is P(s) = sα. We give a nonclairvoyant algorithm that is shown to be O(α3)-competitive. We then show an (α1/3-ε) lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be O(1)-competitive.
DescriptionSession 1A
Persistent Identifierhttp://hdl.handle.net/10722/61186
ISBN
978-3-939897-09-5

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorEdmonds, Jen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorMarchetti-Spaccamela, Aen_HK
dc.contributor.authorPruhs, Ken_HK
dc.date.accessioned2010-07-13T03:32:45Z-
dc.date.available2010-07-13T03:32:45Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), University of Freiburg, Freiburg, Germany, 26-28 February 2009. In Conference Proceedings, 2009, p. 225-264en_HK
dc.identifier.isbn978-3-939897-09-5en_HK
dc.identifier.urihttp://hdl.handle.net/10722/61186-
dc.descriptionSession 1Aen_HK
dc.description.abstractWe study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is P(s) = sα. We give a nonclairvoyant algorithm that is shown to be O(α3)-competitive. We then show an (α1/3-ε) lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be O(1)-competitive.-
dc.languageengen_HK
dc.publisherIBFI Schloss Dagstuhl.-
dc.relation.ispartofProceedings of the 26th International Symposium on Theoretical Aspects of Computer Science-
dc.titleNonclairvoyant speed scaling for flow and energyen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-3-939897-09-5&volume=&spage=225&epage=264&date=2009&atitle=Nonclairvoyant+speed+scaling+for+flow+and+energyen_HK
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailEdmonds, J: jeff@cs.yorku.caen_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hk-
dc.identifier.emailMarchetti-Spaccamela, A: alberto@dis.uniroma1.it-
dc.identifier.emailPruhs, K: kirk@cs.pitt.edu-
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.hkuros163534en_HK
dc.identifier.spage225-
dc.identifier.epage264-
dc.description.otherThe 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), University of Freiburg, Freiburg, Germany, 26-28 February 2009. In Conference Proceedings, 2009, p. 225-264-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats