Tata Institute of Fundamental Research
A Gibbsian Approach to Load Balancing in Large Graphs
STCS Seminar
Speaker:
Rajesh Sundaresan (Indian Institute of Science
Department of Electrical
Communication Engineering
Bangalore 560012)
Organiser:
Vinod M. Prabhakaran
Date:
Thursday, 27 Jul 2017, 11:00 to 12:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Rajesh Sundaresan (Indian Institute of Science Department of Electrical Communication Engineering Bangalore 560012) |
| Organiser: | Vinod M. Prabhakaran |
| Date: | Thursday, 27 Jul 2017, 11:00 to 12:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.