๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On-Line Load Balancing for Related Machines

โœ Scribed by Piotr Berman; Moses Charikar; Marek Karpinski

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
105 KB
Volume
35
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio ' of 3 q 8 f 5.828 for the deterministic version, and 3.31rln 2.155 f 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2 e f 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.

๐Ÿ“œ SIMILAR VOLUMES

On-Line Load Balancing of Temporary Task
On-Line Load Balancing of Temporary Tasks
โœ Yossi Azar; Bala Kalyanasundaram; Serge Plotkin; Kirk R Pruhs; Orli Waarts ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 181 KB

O n -competitive algorithm. In addition, trying to overcome the โ€ n lower bound for the case of unknown task duration, this paper initiates a study of the ลฝ load balancing problem for tasks with known duration i.e., the duration of a task . ลฝ . becomes known upon its arrival . For this case we show

Load balancing for redundant storage str
Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility
โœ Joep Aerts; Jan Korst; Wim Verhaegh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 132 KB

An important cost issue in multimedia servers is disk load balancing, such that the available hard disks are used as e ciently as possible. Disk load balancing is often done on a block basis, but can also be done on a time basis, by taking into account the actual transfer times of the blocks. In the

Load Balancing Using Heterogeneous Proce
Load Balancing Using Heterogeneous Processors for Continuum Problems on a Mesh
โœ Marlin H. Mickle; JoAnn M. Paul ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 242 KB

The results are applicable to any mesh without wrap-around communication. Any difference in shape changes the relative number of type B and type C processors as shown in Fig. 1, i.e., processors with 3 or 4 communication links respectively. The results are applicable to a 3-D mesh or any configurati