School of Technology and Computer Science Seminars

A Gibbsian Approach to Load Balancing in Large Graphs

by Rajesh Sundaresan (Indian Institute of Science, Bangalore)

Thursday, July 27, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.