Efficient schemes for nearest neighbor load balancing

We design a general mathematical framework to analyze the properties of nea rest neighbor balancing algorithms of the diffusion type. Within this frame work we develop a new Optimal Polynomial Scheme (OPS) which we show to term inate within a finite number m of steps, where m only depends on the graph and not on the initial load distribution. We show that all existing diffusion load balancing algorithms, including OP S, determine a flow of load on the edges of the graph which is uniquely def ined, independent of the method and minimal in the l(2)-norm. This result c an also be extended to edge weighted graphs. The l(2)-minimality is achieved only if a diffusion algorithm is used as pr eprocessing and the real movement of load is performed in a second step. Th us, it is advisable to split the balancing process into the two steps of fi rst determining a balancing flow and afterwards moving the load. We introdu ce the problem of scheduling a flow and present some first results on its c omplexity and the approximation quality of local greedy heuristics. (C) 199 9 Published by Elsevier Science B.V. All rights reserved.