English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Scheduling at Twilight the Easy Way

Bast, H. (2002). Scheduling at Twilight the Easy Way. In STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science (pp. 166-178). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bast, Hannah1, Author           
Ferreira, Afonso, Editor
Alt, Helmut, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2003-09-052002
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 202054
Other: Local-ID: C1256428004B93B8-1F797C13238C3EF5C1256B110055EA3D-Bast2002a
 Degree: -

Event

show
hide
Title: STACS 2002
Place of Event: Antibes, Juan-Les-Pins, France
Start-/End Date: 2002-03-14 - 2002-03-16

Legal Case

show

Project information

show

Source 1

show
hide
Title: STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 166 - 178 Identifier: ISBN: 3-540-43283-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2285 Sequence Number: - Start / End Page: - Identifier: -