File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Speed scaling with an arbitrary power function

TitleSpeed scaling with an arbitrary power function
Authors
KeywordsCompetitive algorithms
Power Consumption
Power functions
Processor speed
Speed scaling
Technological advances
Issue Date2009
PublisherSIAM.
Citation
The 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 693-701 How to Cite?
AbstractAll of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption P as a function of the processor speed s, is of the form P = sα, where α > 1 is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a (3+ε)-competitive algorithm for this problem, that holds for essentially any power function. We also give a (2+ε)-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form sα, it was not previously known how to obtain competitiveness independent of a for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature. Copyright © by SIAM.
Persistent Identifierhttp://hdl.handle.net/10722/125690
ISBN
References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorPruhs, Ken_HK
dc.date.accessioned2010-10-31T11:46:15Z-
dc.date.available2010-10-31T11:46:15Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 693-701en_HK
dc.identifier.isbn978-089871680-1-
dc.identifier.urihttp://hdl.handle.net/10722/125690-
dc.description.abstractAll of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption P as a function of the processor speed s, is of the form P = sα, where α > 1 is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a (3+ε)-competitive algorithm for this problem, that holds for essentially any power function. We also give a (2+ε)-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form sα, it was not previously known how to obtain competitiveness independent of a for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature. Copyright © by SIAM.en_HK
dc.languageengen_HK
dc.publisherSIAM.-
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCompetitive algorithms-
dc.subjectPower Consumption-
dc.subjectPower functions-
dc.subjectProcessor speed-
dc.subjectSpeed scaling-
dc.subjectTechnological advances-
dc.titleSpeed scaling with an arbitrary power functionen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.description.naturepostprint-
dc.identifier.scopuseid_2-s2.0-70349086103en_HK
dc.identifier.hkuros181819en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70349086103&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage693en_HK
dc.identifier.epage701en_HK
dc.description.otherThe 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 693-701-
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridPruhs, K=6603866438en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats