Efficient schemes for nearest neighbor load balancing (Q5896750)

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 its complexity and the approximation quality of local greedy heuristics.