Nonclairvoyant Speed Scaling for Flow and Energy
Nonclairvoyant Speed Scaling for Flow and Energy
复制标题
流量和能量的非透视速度缩放
DOI：
10.1007/s00453-010-9420-2
复制
发表时间：
2009
期刊：
影响因子：
1.1
通讯作者：
K. Pruhs
中科院分区：
文献类型：
--
作者：
H. Chan;J. Edmonds;T. Lam;Lap;A. Marchetti;K. Pruhs
我们给出了三个与在线非行列速度缩放有关的结果，以最大程度地减少总流动时间加能量。更确切地说，对于α= 3，竞争比为8，$ \ frac {2 \ alpha^{2}} {\ ln \ alpha} $forα> 3。没有恒定的c，没有确定性的非行列算法，因此对于p（s）=sα的每个功率函数都是c竞争激烈的我们表明，有一个固定的，非常钢制的功能，没有非透明算法可以是o（1）竞争。
We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=sα, LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and $\frac{2\alpha^{2}}{\ln\alpha}$ for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=sα. So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive.