File Download
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Speed scaling with an arbitrary power function
Title  Speed scaling with an arbitrary power function 

Authors  
Keywords  Competitive algorithms Power Consumption Power functions Processor speed Speed scaling Technological advances 
Issue Date  2009 
Publisher  SIAM. 
Citation  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2009, p. 693701 How to Cite? 
Abstract  All 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 Identifier  http://hdl.handle.net/10722/125690 
ISBN  
References 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Pruhs, K  en_HK 
dc.date.accessioned  20101031T11:46:15Z   
dc.date.available  20101031T11:46:15Z   
dc.date.issued  2009  en_HK 
dc.identifier.citation  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2009, p. 693701  en_HK 
dc.identifier.isbn  9780898716801   
dc.identifier.uri  http://hdl.handle.net/10722/125690   
dc.description.abstract  All 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.language  eng  en_HK 
dc.publisher  SIAM.   
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.subject  Competitive algorithms   
dc.subject  Power Consumption   
dc.subject  Power functions   
dc.subject  Processor speed   
dc.subject  Speed scaling   
dc.subject  Technological advances   
dc.title  Speed scaling with an arbitrary power function  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.description.nature  postprint   
dc.identifier.scopus  eid_2s2.070349086103  en_HK 
dc.identifier.hkuros  181819  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.070349086103&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  693  en_HK 
dc.identifier.epage  701  en_HK 
dc.description.other  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2009, p. 693701   
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Pruhs, K=6603866438  en_HK 