University of Cambridge > Talks.cam > Probability > Rounding Markov Chains and Iterative Load-Balancing Schemes

Rounding Markov Chains and Iterative Load-Balancing Schemes

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity