Nonclairvoyant Speed Scaling for Flow and Energy

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(alpha), LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for alpha = 2, 13 for alpha = 3, and 2 alpha(2)/ln alpha alpha > 3. We then show that there is no constant c, and no deterministic nonclair-voyant algorithm A, such that A is c-competitive for every power function of the form P(s) = s(alpha). 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.