Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:New Results for Non-Preemptive Speed Scaling
Speaker:Sebastian Ott
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 23 September 2014
Duration:30 Minutes
Building:E1 4
Please note: New Room!
We consider the speed scaling problem, where a number of jobs, each with its own processing volume, release time, and deadline, needs to be executed on a single speed-scalable processor. The power consumption of this processor is P(s) = s^α, where s is the processing speed, and α > 1 is a constant. Our goal is to feasibly process all jobs, while minimizing the total energy consumption.

The preemptive version of the problem, along with its many variants, has been extensively studied over the years. However, little is known about the non-preemptive version of the problem, except that it is strongly NP-hard and allows a (large) constant factor approximation. Up until now, the (general) complexity of this problem is unknown. We study an important special case of the problem, where the job intervals form a laminar family, and present a quasipolynomial-time approximation scheme for it. Furthermore, we show that the special case of equal-volume jobs can be solved in polynomial-time.

Name(s):Sebastian Ott
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Sebastian Ott, 09/16/2014 10:30 AM
  • Sebastian Ott, 09/15/2014 03:38 PM -- Created document.