BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Balls-into-Bins via Local Search - Thomas Sauerwald (University of
  Cambridge)
DTSTART:20141113T143000Z
DTEND:20141113T153000Z
UID:TALK55746@talks.cam.ac.uk
CONTACT:Andrew Thomason
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 unif
 ormly at random. Then the ball performs a local search in G starting from 
 u until it reaches a vertex with local minimum load\,\nwhere the ball is f
 inally placed on. Then the next ball arrives and this procedure is repeate
 d. For the case m = n\, we give an upper bound for the maximum load on gra
 phs with bounded degrees. We also propose the study of the cover time of t
 his process\, which is defined as the\nsmallest m so that every bin has at
  least one ball allocated to it. We establish an upper bound for the cover
  time on graphs with bounded degrees. Our bounds for the maximum load and 
 the cover time are tight when the graph is transitive or sufficiently homo
 geneous. We also give upper bounds for the maximum load when m > n.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR