A Gibbsian Approach to Load Balancing in Large Graphs

Speaker: 

Rajesh Sundaresan

Affiliation: 

Indian Institute of Science
Department of Electrical
Communication Engineering
Bangalore 560012

Time: 

Thursday, 27 July 2017, 11:00 to 12:00

Venue: 

Organisers: 

The talk will be on load balancing on a large graph. A unit of load on each edge of a graph is to be distributed between its nodes in a balanced way. On infinite graphs, it is known that the problem exhibits nonuniqueness. Recently, Anantharam and Salez extended the definition of balanced allocations on finite graphs to their local weak limits by exploiting the notion of unimodularity. They used this to settle a conjecture of Hajek on the Erdos-Renyi model. A more classical Gibbsian approach can also be used to arrive at the same result. This talk will highlight the key steps needed to make the classical approach work.