MPI-INF D1 Publications: Electronic Proceedings Article: Nonclairvoyant Speed Scaling for Flow and Energy

Electronic Proceedings Article
@InProceedings
Internet-Beitrag in Tagungsband, Workshop

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor

Author(s):

Chan, Ho-Leung
Edmonds, Jeff
Lam, Tak-Wah
Lee, Lap-Kei
Marchetti-Spaccamela, Alberto
Pruhs, Kirk

dblp
dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Edmonds, Jeff
Lam, Tak-Wah
Lee, Lap-Kei
Marchetti-Spaccamela, Alberto
Pruhs, Kirk

Editor(s):

Albers, Susanne
Marion, Jean-Yves

dblp
dblp

Not MPII Editor(s):

Albers, Susanne
Marion, Jean-Yves

BibTeX cite key*:

Chan2008c

Title, Conference

Title*:	Nonclairvoyant Speed Scaling for Flow and Energy
Booktitle*:	Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)
Event Address*:	Freiburg, Germany	URL of the conference:
Event Date*: (no longer used):		URL for downloading the paper:	http://drops.dagstuhl.de/opus/volltexte/2009/1815/
Event Start Date:	26 February 2009	Event End Date:	28 February 2009
Language:	English	Organization:

Publisher

Publisher's Name:	LZI	Publisher's URL:
Address*:	Dagstuhl, Germany	Type:

Vol, No, pp., Year

Series:	Leibniz International Proceedings in Informatics
Volume:	3	Number:
Month:		Pages:	255-264
		Sequence Number:
Year*:	2009	ISBN/ISSN:	978-3-939897-09-5
	10.4230/LIPIcs.STACS.2009.1815

Abstract, Links, ©

URL for Reference:
Note:
(LaTeX) Abstract:	We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O( \alpha^3 )$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.
URL for the Abstract:

Tags, Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:	The rights on the articles in the proceedings are kept with the authors and the papers are available freely, under a Creative Commons license (see www.stacs-conf.org/faq.html for more details)
Personal Comments:	URN: urn:nbn:de:0030-drops-18151 DROPS is the Dagstuhl Research Online Publication Server
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{Chan2008c,
AUTHOR = {Chan, Ho-Leung and Edmonds, Jeff and Lam, Tak-Wah and Lee, Lap-Kei and Marchetti-Spaccamela, Alberto and Pruhs, Kirk},
EDITOR = {Albers, Susanne and Marion, Jean-Yves},
TITLE = {Nonclairvoyant Speed Scaling for Flow and Energy},
BOOKTITLE = {Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)},
PUBLISHER = {LZI},
YEAR = {2009},
VOLUME = {3},
PAGES = {255--264},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {Freiburg, Germany},
ISBN = {978-3-939897-09-5},
ISBN = {1868-8969},
DOI = {10.4230/LIPIcs.STACS.2009.1815},
}

Entry last modified by Anja Becker, 03/08/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 03/21/2009 16:34:38
Revisions 4. 3. 2. 1. 0.	Editor(s) Anja Becker Anja Becker Anja Becker Anja Becker Anja Becker	Edit Dates 08.03.2010 14:14:38 05.03.2010 15:20:55 05.03.2010 15:20:20 04.03.2010 11:50:57 2009/03/21 下午 04:34:38

Attachment Section