Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  New Results for Non-preemptive Speed Scaling

Huang, C.-C., & Ott, S.(2013). New Results for Non-preemptive Speed Scaling (MPI-I-2013-1-001). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-2013-1-001.pdf (beliebiger Volltext), 290KB
Name:
MPI-I-2013-1-001.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Huang, Chien-Chung1, Autor           
Ott, Sebastian2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We consider the speed scaling problem introduced in the seminal paper of Yao et al.. In this problem, a number of jobs, each with its own processing volume, release time, and deadline needs to be executed on a speed-scalable processor. The power consumption of this processor is $P(s) = s^\alpha$, where $s$ is the processing speed, and $\alpha > 1$ is a constant. The total energy consumption is power integrated over time, and the goal is to process all jobs while minimizing the 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 constant factor approximation. Up until now, the (general) complexity of this problem is unknown. In the present paper, 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, thereby showing that (at least) this special case is not APX-hard, unless $NP \subseteq DTIME(2^{poly(\log n)})$. The second contribution of this work is a polynomial-time algorithm for the special case of equal-volume jobs, where previously only a $2^\alpha$ approximation was known. In addition, we show that two other special cases of this problem allow fully polynomial-time approximation schemes (FPTASs).

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2013
 Publikationsstatus: Online veröffentlicht
 Seiten: 32 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-2013-1-001
BibTex Citekey: HuangOtt2013
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Reports
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0946-011X