Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Pruhs, Kirk
van Stee, Rob
Uthaisombut, Patchrawat

dblp
dblp
dblp

Not MPG Author(s):

Pruhs, Kirk
Uthaisombut, Patchrawat

BibTeX cite key*:

vanStee2008h

Title

Title*:

Speed Scaling of Tasks with Precedence Constraints


precede-j5.ps (246.96 KB)

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://www.springerlink.com/content/100369/?p=c26d3b566615481c9a1252cd6bb1404c&pi=0

Download URL
for the article:

http://www.springerlink.com/content/x28960820041k300/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

Berlin

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

43

Number:

1

Publishing Date:

July 2008

Pages*:

67-80

Number of
VG Pages:

14

Page Start:


Page End:


Sequence Number:


DOI:

10.1007/s00224-007-9070-1

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider the problem of speed scaling to conserve energy in a multiprocessor setting
where there are precedence constraints between tasks, and where the performance measure
is the makespan.
That is, we consider an energy bounded version of the classic problem
$Pm \mid prec \mid C_{max}$.
We extend the standard 3-field notation and denote this problem as
$Sm \mid prec, \, energy \mid C_{\max}$.
We show that, without loss of generality, one need only consider constant power
schedules. We then show how to reduce this problem to the problem
$Qm \mid prec \mid C_{max}$ to obtain a poly-log($m$)-approximation algorithm.

URL for the Abstract:


Categories,
Keywords:

scheduling, approximation algorithms, precedence constraints

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{vanStee2008h,
AUTHOR = {Pruhs, Kirk and van Stee, Rob and Uthaisombut, Patchrawat},
TITLE = {Speed Scaling of Tasks with Precedence Constraints},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2008},
NUMBER = {1},
VOLUME = {43},
PAGES = {67--80},
ADDRESS = {Berlin},
MONTH = {July},
ISBN = {1432-4350},
DOI = {10.1007/s00224-007-9070-1},
}


Entry last modified by Rob van Stee, 03/03/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rob van Stee
Created
01/12/2009 01:25:46 PM
Revision
0.



Editor
Rob van Stee



Edit Date
01/12/2009 01:25:47 PM



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
precede-j5.ps