Nonclairvoyant Speed Scaling for Flow and Energy

Details Nonclairvoyant Speed Scaling for Flow and Energy Nonclairvoyant Speed Scaling for Flow and Energy

2009-02-07

arxiv.org/abs/0902.1260v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 255-264

Computer Science

Data Structures and Algorithms

Scientific paper

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\^\propto. We give a nonclairvoyant algorithm that is shown to be O(\propto\^3)-competitive. We then show an \Omega(\propto\^(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.

Affiliated with

Also associated with

No associations

Rating

Nonclairvoyant Speed Scaling for Flow and Energy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonclairvoyant Speed Scaling for Flow and Energy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonclairvoyant Speed Scaling for Flow and Energy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312193