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:








Author, Editor

Author(s):

Bast, Hannah

dblp



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

URL of the conference:

http://www-sop.inria.fr/stacs2002/

URL for downloading the paper:


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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section