Ancient and New Algorithms for Load Balancing in the L_p Norm

We consider the on-line load balancing problem where there are m identical machines (servers) and a sequence of jobs. The jobs arrive one by one and should be assigned to one of the machines in an online fashion. The goal is to minimize the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. We show that for the sum of the squares the greedy algorithm performs within 4=3 of the optimum, and no on-line algorithm achieves a better competitive ratio. Interestingly, we show that the performance of greedy is not monotone in the number of machines. More specifically, the competitive ratio is 4=3 for any number of machines divisible by 3 but strictly less than 4=3 in all the other cases (although it approaches 4=3 for large number of machines). To prove that greedy is optimal, we show a the lower bound of 4=3 for any algorithm for 3 machines. Surprisingly, we provide a new on-line algorithm that performs within 4=3 \Gamma ffi of the optimum, for some ..