Load balancing and random graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1