Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms
Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms
复制标题
DOI：
10.1145/3155297
复制
发表时间：
2014-01
期刊：
影响因子：
--
通讯作者：
Nikhil R. Devanur;Zhiyi Huang
中科院分区：
文献类型：
--
作者：
Nikhil R. Devanur;Zhiyi Huang
我们考虑通过动态速度缩放在不相关的机器上在线调度作业的问题，以最小化能量和加权流动时间的总和。我们给出了一种对于任意幂函数具有几乎最佳竞争比的算法。 （早期结果没有处理不相关机器的任意幂函数。）对于 f(s) = sα 形式的幂函数，对于某个常数 α > 1，我们得到 O(α / log α) 的竞争比，改进了 Anand 等人之前提出的 O(α2) 竞争比。 (2012)，以及匹配的 Ω(α / log α) 下限。此外，在资源增强模型中，随着 1+ ε 的加速，我们给出了 2(1/ε + 1) 竞争算法，使用基本相同的技术，提高了 Gupta 等人的 1 + O(1/ε2) 的界限。 (2010) 并匹配 Anand 等人的界限。 (2012) 对于固定速度无关机器的特殊情况。与之前的结果大多数使用摊销局部竞争力参数或对偶拟合方法不同，我们使用原始对偶方法，该方法不仅可用于分析算法，而且还可用于设计算法本身。
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 unrelated machines.) For power functions of the form f(s) = sα for some constant α > 1, we get a competitive ratio of O(α / log α), improving upon a previous competitive ratio of O(α2) by Anand et al. (2012), along with a matching lower bound of Ω(α / log α). Further, in the resource augmentation model, with a 1+ ε speed up, we give a 2(1/ε + 1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1/ε2) by Gupta et al. (2010) and matching the bound of Anand et al. (2012) 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 primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.