|
Friday, July 3, 2009 |
|
|
|
|
Load balancing and random graphs |
|
|
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. |