Efficient schemes for nearest neighbor load balancing

✍ Scribed by Ralf Diekmann; Andreas Frommer; Burkhard Monien

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 282 KB
• Volume: 25
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(99)00018-6

✦ Synopsis

We design a general mathematical framework to analyze the properties of nearest neighbor balancing algorithms of the diusion type. Within this framework we develop a new Optimal Polynomial Scheme (OPS) which we show to terminate within a ®nite number m of steps, where m only depends on the graph and not on the initial load distribution.

We show that all existing diusion load balancing algorithms, including OPS, determine a ¯ow of load on the edges of the graph which is uniquely de®ned, 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 diusion 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 ®rst determining a balancing ¯ow and afterwards moving the load. We introduce the problem of scheduling a ¯ow and present some ®rst results on its complexity and the approximation quality of local greedy heuristics.