School Seminars and Colloquia

Load balancing and random graphs

Discrete Structures and Algorithms (Seminar)

by Professor Nick Wormald


Institution: Department of Combinatorics and Optimization, Waterloo University, Canada
Date: Tue 30th March 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: 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.

For More Information: contact: David Wood. email woodd@unimelb.edu.au