MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Bast, Hannahdblp
Editor(s):
Ferreira, Afonso
Alt, Helmut
dblp
dblp
Not MPII Editor(s):
Ferreira, Afonso
Alt, Helmut
BibTeX cite key*:
Bast2002a
Title, Booktitle
Title*:
Scheduling at Twilight the Easy Way
Booktitle*:
STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science
Event, URLs
Conference URL::
http://www-sop.inria.fr/stacs2002/
Downloading URL:
Event Address*:
Antibes, Juan-Les-Pins, France
Language:
English
Event Date*
(no longer used):
-- March, 14 - 16
Organization:
Event Start Date:
14 March 2002
Event End Date:
16 March 2002
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2285
Number:
Month:
March
Pages:
166-178
Year*:
2002
VG Wort Pages:
22
ISBN/ISSN:
3-540-43283-3
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We investigate particularly simple algorithms for optimizing the tradeoff
between load imbalance and assignment overheads in dynamic multiprocessor
scheduling scenarios, when the information that is available about the processing time of a task before it is completed is vague.
We describe a simple and elegant generic algorithm that, in a very
general model, always comes surprisingly close to the theoretical optimum,
and the performance of which we can analyze exactly with respect to constant
factors. In contrast, we prove that algorithms that assign tasks
in equal-sized portions
perform far from optimal in general. In fact, we give evidence that the
performance of our generic scheme cannot be improved by any constant factor
without sacrificing the simplicity of the algorithm. We also give lower
bounds on the performance of the various decreasing-size heuristics that
have typically been used so far in concrete applications.
URL for the Abstract:
http://link.springer.de/link/service/series/0558/bibs/2285/22850166.htm
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{Bast2002a,
AUTHOR = {Bast, Hannah},
EDITOR = {Ferreira, Afonso and Alt, Helmut},
TITLE = {Scheduling at Twilight the Easy Way},
BOOKTITLE = {STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2285},
PAGES = {166--178},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Antibes, Juan-Les-Pins, France},
MONTH = {March},
ISBN = {3-540-43283-3},
}


Entry last modified by Christine Kiesel, 03/02/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)
Hannah Bast
Created
11/27/2001 04:38:25 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Christine Kiesel
Christine Kiesel
Anja Becker
Anja Becker
Anja Becker
Edit Dates
05.09.2003 19:18:55
27.08.2003 17:09:26
26.06.2003 14:25:30
26.06.2003 14:19:21
09.05.2003 12:22:28