Electronic Proceedings Article
@InProceedings
Internet-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):

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
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
03/21/2009 04:34:38 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section