BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Balls-into-Bins via Local Search - Thomas Sauerwal
d (University of Cambridge)
DTSTART;TZID=Europe/London:20141113T143000
DTEND;TZID=Europe/London:20141113T153000
UID:TALK55746AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/55746
DESCRIPTION:We study a natural process for allocating m balls
into n bins that are organized as the vertices of
an undirected graph G. Balls arrive one at a time.
When a ball arrives\, it first chooses a vertex u
in G uniformly at random. Then the ball performs
a local search in G starting from u until it reach
es a vertex with local minimum load\,\nwhere the b
all is finally placed on. Then the next ball arriv
es and this procedure is repeated. For the case m
= n\, we give an upper bound for the maximum load
on graphs with bounded degrees. We also propose th
e study of the cover time of this process\, which
is defined as the\nsmallest m so that every bin ha
s at least one ball allocated to it. We establish
an upper bound for the cover time on graphs with b
ounded degrees. Our bounds for the maximum load an
d the cover time are tight when the graph is trans
itive or sufficiently homogeneous. We also give up
per bounds for the maximum load when m > n.\n
LOCATION:MR12
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR