Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 202054.0, MPI für Informatik / Algorithms and Complexity Group
Scheduling at Twilight the Easy Way
Authors:Bast, Hannah
Editors:Ferreira, Afonso; Alt, Helmut
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science
Start Page:166
End Page:178
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Antibes, Juan-Les-Pins, France
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-03-14
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2003-09-05
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:ISBN:3-540-43283-3
LOCALID:C1256428004B93B8-1F797C13238C3EF5C1256B110055EA3D-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.