Load Balancing in Large Graphs

Seminar
Friday, March 21, 2014
11:00am
ENS 637

In this discussion 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 with 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ös-Rényi 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. 
 
This research represents a joint work with Justin Salez from the Université Paris Diderot. 

Speaker

Professor
University of California - Berkeley

Venkat Anantharam is a professor in the Electrical Engineering and Computer Sciences 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.