DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

                   Resource Augmentation in Load Balancing                   

                                 Rob van Stee                                
                                     CWI                                     

                     Tuesday, June 27, 2000, at 12:30 PM                     
                               The Seminar Room                              


We consider load balancing in the  following setting.  The on-line algorithm
is allowed to  use n  machines, whereas  the optimal  off-line algorithm  is
limited to m machines, for some fixed m  < n.  We show that while the greedy
algorithm has a competitive  ratio which decays  linearly in the  inverse of
n/m, the best on-line  algorithm has a  ratio which decays  exponentially in
n/m.  Specifically, we  give an  algorithm  with competitive  ratio  of 1  +
1/2^((n/m)(1-o(1))), and a  lower bound  of 1  + 1/e^((n/m)(1+o(1)))  on the
competitive ratio of any randomized algorithm.

We also consider the preemptive  case.  We show an on-line  algorithm with a
competitive ratio of 1 + 1/e^((n/m)(1+o(1))).  We show that the algorithm is
optimal by proving a matching lower bound.
 
We also consider  the non-preemptive model  with temporary  tasks.  We prove
that for n = m+1,  the greedy algorithm is optimal.  (It  is not optimal for
permanent tasks).

This is joint work with Yossi Azar and Leah Epstein.


                                                       Host: Kim Skak Larsen