We design a general mathematical framework to analyze the properties of nearest neighbor balancing algorithms of the diffusion
type. Within this framework we develop a new
optimal polynomial scheme (OPS) which we show to terminate 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 OPS determine a flow of load on the edges of the
graph which is uniquely defined, independent of the method and minimal in the l
2-norm. This result can also be extended to edge weighted graphs.
The l
2-minimality is achieved only if a diffusion algorithm is used as preprocessing and the real movement of load is performed
in a second step. Thus, it is advisable to split the balancing process into the two steps of first determining a balancing
flow and afterwards moving the load. We introduce the problem of scheduling a flow and present some first results on the approximation
quality of local greedy heuristics.
Partly supported by the DFG-Sonderforschungsbereich 376 “Massive Parallelität: Algorithmen, Entwurfsmethoden, Anwendungen”
and the EC ESPRIT Long Term Research Project 20244 (ALCOM-IT).