Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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, Claire

dblp

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

URL of the conference:

http://www.siam.org/meetings/da09/

URL for downloading the paper:

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
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)
[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

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