File Download
Supplementary

Conference Paper: Nonclairvoyant speed scaling for flow and energy

TitleNonclairvoyant speed scaling for flow and energy
Authors
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

 

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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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