A general problem area involves job assignments. There is a set of jobs to be assigned to processors (i.e. things that can deal with the jobs).
We wish to assign the jobs such that, roughly speaking, all processors are kept as busy as possible. Various problems arise by imposing different constraints and objective functions can be imposed. 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.
Copyright. All Rights Reserved.