Ancient and new algorithms for load balancing in the l(p) norm

We consider the on-line load balancing problem where there are in 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 on-line fashion. The goal i s to minimize the sum (over all machines) of the squares of the loads, inst ead of the traditional maximum load. We show that for the sum of the squares the greedy algorithm performs withi n 4/3 of the optimum, and no on-line algorithm achieves a better competitiv e ratio. Interestingly, we show that the performance of Greedy is not monot one 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 a large number of mach ines). To prove that Greedy is optimal, we show a lower bound of 4/3 for an y algorithm for three machines. Surprisingly, we provide a new on-line algo rithm that performs within 4/3 - delta of the optimum, for some fixed delta > 0, for any sufficiently large number of machines. This implies that the asymptotic competitive ratio of our new algorithm is strictly better than t he competitive ratio of any possible on-line algorithm. Such phenomena is n ot known to occur for the classic maximum load problem. Minimizing the sum of the squares is equivalent to minimizing the load vect or with respect to the l(2) norm. We extend our techniques and analyze the exact competitive ratio of Greedy with respect to the l(p) norm. This ratio turns out to be 2 - Theta((ln p)/p). We show that Greedy is optimal for tw o machines but design an algorithm whose asymptotic competitive ratio is be tter than the ratio of Greedy.