MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Bansal, Nikhil
Chan, Ho-Leung
Pruhs, Kirk
dblp
dblp
dblp
Not MPG Author(s):
Bansal, Nikhil
Pruhs, Kirk
Editor(s):
Mathieu, Clairedblp
Not MPII Editor(s):
Mathieu, Claire
BibTeX cite key*:
Chan2008b
Title, Booktitle
Title*:
Speed Scaling with an Arbitrary Power Function
Booktitle*:
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da09/
Downloading URL:
http://www.siam.org/proceedings/soda/2009/soda09.php
Event Address*:
New York, USA
Language:
English
Event Date*
(no longer used):
Organization:
ACM-SIAM
Event Start Date:
4 January 2009
Event End Date:
6 January 2009
Publisher
Name*:
ACM
URL:
Address*:
New York, NY
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
693-701
Year*:
2009
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
All of the theoretical speed scaling research to date has assumed that the
power function, which expresses the power consumption $P$ as a function
of the processor speed $s$,
is of the form $P=s^\alpha$, where $\alpha > 1$ is some constant.
Motivated in part by technological advances,
we initiate a study of speed scaling with arbitrary
power functions.
We consider the problem of minimizing the total flow plus energy.
Our main result is a $(3+\epsilon)$-competitive algorithm for this problem, that holds
for essentially any power function.
We also give a $(2+\epsilon)$-competitive algorithm for the objective of
fractional weighted flow plus energy.
Even for power functions of the form $s^\alpha$, it was not previously
known how to obtain competitiveness independent of $\alpha$ for
these problems.
We also introduce a model of allowable speeds that generalizes
all known models in the literature.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Chan2008b,
AUTHOR = {Bansal, Nikhil and Chan, Ho-Leung and Pruhs, Kirk},
EDITOR = {Mathieu, Claire},
TITLE = {Speed Scaling with an Arbitrary Power Function},
BOOKTITLE = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)},
PUBLISHER = {ACM},
YEAR = {2009},
ORGANIZATION = {ACM-SIAM},
PAGES = {693--701},
ADDRESS = {New York, USA},
}


Entry last modified by Anja Becker, 03/04/2010
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)
[Library]
Created
01/29/2009 11:08:50 AM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Ho-Leung Chan
Ho-Leung Chan

Edit Dates
01.03.2010 13:12:18
2009/03/21 下午 04:25:15
2009/01/29 上午 11:08:50