Consider a process in which m tasks are assigned one by one, each to one of n servers, positioned at the vertices of an n vertex, d(n)-regular graph G=(V,E).
Whenever a task arrives, a random edge (v,u) in E is selected and an overseer is allowed to assign the task either to u or v. The load of every server is the number of tasks assigned to it.
The purpose of the overseer is to reduce the maximum load to be as close as possible to the average load m/n. We call the difference between these numbers gap(m).

In the case G=K_n classical "power of two choices" results show that the greedy algorithm obtains an optimal gap(m) of \theta(log log m).

Later results by Peres, Talwar and Wieder, show that, on expanders, the greedy algorithm obtains an optimal gap(m) of \theta(log m). It is conjectured that this result holds for a much wider class of highly connected graphs. However, on general d connected graphs, such as the cycle graph, the greedy algorithm appears to perform poorly.

In a recent work with Nikhil Bansal we show that an efficient global non-greedy algorithm, based on the celebrated Räcke decomposition, achieves \theta(log^4 m) gap for any such graph. Our work relates the problem to flow problems and is inspired by techniques from discrepancy theory.

No prior knowledge on any of the topics is assumed.