Tutte seminar - Nick Wormald

Load balancing and random graphs

Abstract:

Many problems involve assigning a set of jobs to a set of processors (i.e. things that can deal with the jobs). Load balancing becomes involved if we wish to assign the jobs such that, roughly speaking, all processors are kept equally busy. Various problems arise by imposing different constraints and objective functions. I will discuss some of these, and in particular, a connection to a problem concerning orientations of graphs or hypergraphs. Thus, when can a graph's edges be oriented so that the maximum indegree is at most k? How can we find such an orientation quickly? This setting gives rise to problems on thresholds, and algorithms, for random graphs and hypergraphs. 

The talk will include some recent work with Jane Gao.