Load Balancing in Large Graphs

We consider load balancing on a large graph. Each edge has a unit of load that it wishes to distribute between its nodes in the most balanced way. For infinite graphs the corresponding load balancing problem exhibits nonuniqueness, related to role of boundary conditions in statistical mechanical models.

Nevertheless, we are able to extend the notion of balanced loads from large finite graphs to their local weak limits, using the concept of unimodularity. The result applies in particular to the Erd"os-R'enyi model, where it settles a conjecture of Hajek (1990).  Our proof is a new illustration of the objective method described by Aldous and Steele (2004).

All the necessary background from the machinery of local weak convergence that is needed will be developed during the talk. This machinery provides a way to study many problems of applied interest in large networks beyond just the load balancing problem that will be the focus of this talk. It is therefore valuable to familiarize oneself with this theory if one is interested in understanding the behavior of large networks such as wired and wireless networks, transportation networks, and social networks (joint work with Justin Salez, Universit'e Paris Diderot).

Bio: Venkat Anantharam is on the faculty of the EECS Department at the University of California, Berkeley. He received the Philips India Medal and the President of India Gold Medal from IIT Madras in 1980 and an NSF Presidential Young Investigator award in 1988. He is a corecipient of the 1998 Prize Paper Award of the IEEE Information Theory Society, and a corecipient of the 2000 Stephen O. Rice Prize Paper Award of the IEEE Communications Theory Society. He received the Distinguished Alumnus Award from IIT Madras in 2008.