MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Tight Analysis of Randomized Rumor Spreading in Complete Graphs

Marvin Künnemann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 12 December 2013
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We present a tight analysis of the basic randomized rumor spreading process in complete graphs introduced by Frieze and Grimmett (1985), where in each round of the process each node knowing the rumor gossips the rumor to a node chosen uniformly at random. The process starts with a single node knowing the rumor.


We show that the number S_n of rounds required to spread a rumor in a complete graph with n nodes is very closely described by log_2(n) plus (1/n) times the completion time of the coupon collector process. This in particular gives very precise bounds for the expected runtime of the process, namely floor(log_2(n)) + ln(n) - 1.116 <= E[S_n] <= ceil(log_2(n)) + ln(n) + 2.765 + o(1).

This is joint work with Benjamin Doerr.

Contact

Marvin Künnemann
--email hidden
passcode not visible
logged in users only

Marvin Künnemann, 12/03/2013 20:25 -- Created document.