文章基本信息

标题：Nonclairvoyant Speed Scaling for Flow and Energy
本地全文：下载
作者：Ho-Leung Chan ; Jeff Edmonds ; Tak-Wah Lam 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：255-264
DOI：10.4230/LIPIcs.STACS.2009.1815
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.