AG 1, AG 3, AG 5, SWS, AG 2, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

We study online nonclairvoyant speed scaling to minimze total flow time plus energy. We first consider the traditional model where the power funtion is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that we show is $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 are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.

Ho-Leung Chan

--email hidden

passcode not visible

logged in users only