Load Balancing in the Lp Norm
Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming Kao, P. Krishnan, Jeffrey Scott Vitter · 1995
In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion. Traditionally, the assignment of jobs to servers is measured by the L1 norm; in other words, an assignment of jobs to servers is quantified by the maximum load assigned to any server. In this measure the performance of the greedy load balancing algorithm may be a logarithmic factor higher than optimal [3]. In many applications, the L1 norm is not a suitable way to measure how well the jobs are balanced. If each job sees a delay that is proportional to the number of jobs on its server, then the average delay among all jobs is proportional to the sum of the squares of the numbers of jobs assigned to the servers. Minimizing the average delay is equivalent to minimizing the Euclidean (or L 2 ) norm. For any fixed p, 1 p ! 1, we show that the greedy algorithm performs within a constant factor of...