BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Rounding Markov Chains and Iterative Load-Balancing Schemes - Dr T
 homas Sauerwald\, Computer Laboratory\, University of Cambridge 
DTSTART:20140520T153000Z
DTEND:20140520T163000Z
UID:TALK52440@talks.cam.ac.uk
CONTACT:37296
DESCRIPTION:Iterative Load-Balancing Schemes allow nodes to balance its lo
 ad with\ntheir neighbors in each iteration. Under the assumption that load
  can be\ndivided arbitrarily often (continuous case)\, it is well-known th
 at such\nschemes correspond to Markov chains whose convergence is characte
 rised\nby the spectral gap of the transition matrix. In this talk we focus
  on\nthe discrete case where load is integral. We show that by employing\n
 randomised rounding\, the system converges to a state where all nodes\nhav
 e the same load up to an additive constant within the same number of\nstep
 s that are needed in the continuous case.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR