Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1137/1.9781611973402.83
 Scopus: eid_2s2.084902108766
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Primal dual gives almost optimal energy efficient online algorithms
Title  Primal dual gives almost optimal energy efficient online algorithms 

Authors  
Issue Date  2014 
Publisher  Society for Industrial and Applied Mathematics (SIAM). 
Citation  The 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR., 57 January 2014. In Conference Proceedings, 2014, p. 11231140 How to Cite? 
Abstract  We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for minimizing flow time plus energy with unrelated machines.) For power functions of the form f(s) = s^alpha for some constant alpha > 1, we get a competitive ratio of O(alpha/log(alpha)), improving upon a previous competitive ratio of O(alpha^2) by Anand et al., along with a matching lower bound of . Further, in the resource augmentation model, with a 1+epsilon speed up, we give a O(1/epsilon) competitive algorithm, with essentially the same techniques, improving the bound of O(1/epsilon^2) by Gupta et al. and matching the bound of Anand et al. [3] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primaldual method, which is useful not only to analyze the algorithms but also to design the algorithm itself. Copyright © 2014 by the Society for Industrial and Applied Mathematics. 
Persistent Identifier  http://hdl.handle.net/10722/201111 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Devanur, NR  en_US 
dc.contributor.author  Huang, Z  en_US 
dc.date.accessioned  20140821T07:13:35Z   
dc.date.available  20140821T07:13:35Z   
dc.date.issued  2014  en_US 
dc.identifier.citation  The 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2014), Portland, OR., 57 January 2014. In Conference Proceedings, 2014, p. 11231140  en_US 
dc.identifier.isbn  9781611973389   
dc.identifier.uri  http://hdl.handle.net/10722/201111   
dc.description.abstract  We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for minimizing flow time plus energy with unrelated machines.) For power functions of the form f(s) = s^alpha for some constant alpha > 1, we get a competitive ratio of O(alpha/log(alpha)), improving upon a previous competitive ratio of O(alpha^2) by Anand et al., along with a matching lower bound of . Further, in the resource augmentation model, with a 1+epsilon speed up, we give a O(1/epsilon) competitive algorithm, with essentially the same techniques, improving the bound of O(1/epsilon^2) by Gupta et al. and matching the bound of Anand et al. [3] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primaldual method, which is useful not only to analyze the algorithms but also to design the algorithm itself. Copyright © 2014 by the Society for Industrial and Applied Mathematics.  en_US 
dc.language  eng  en_US 
dc.publisher  Society for Industrial and Applied Mathematics (SIAM).   
dc.relation.ispartof  Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms  en_US 
dc.title  Primal dual gives almost optimal energy efficient online algorithms  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Huang, Z: hzhiyi@hku.hk  en_US 
dc.identifier.authority  Huang, Z=rp01804  en_US 
dc.description.nature  link_to_OA_fulltext   
dc.identifier.doi  10.1137/1.9781611973402.83  en_US 
dc.identifier.scopus  eid_2s2.084902108766   
dc.identifier.hkuros  234389  en_US 
dc.identifier.spage  1123   
dc.identifier.epage  1140   
dc.publisher.place  United States   
dc.customcontrol.immutable  sml 141016   