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 Goto entry point

 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:

 (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
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