Rounding Markov Chains and Iterative Load-Balancing Schemes

Add to your list(s) Download to your calendar using vCal

• Dr Thomas Sauerwald, Computer Laboratory, University of Cambridge
• Tuesday 20 May 2014, 16:30-17:30
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact clc32.

Iterative Load-Balancing Schemes allow nodes to balance its load with their neighbors in each iteration. Under the assumption that load can be divided arbitrarily often (continuous case), it is well-known that such schemes correspond to Markov chains whose convergence is characterised by the spectral gap of the transition matrix. In this talk we focus on the discrete case where load is integral. We show that by employing randomised rounding, the system converges to a state where all nodes have the same load up to an additive constant within the same number of steps that are needed in the continuous case.

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.