Title: Unbalanced allocations
Speaker: Amanda Redlich, MIT
Date: Thursday, April 22, 2010 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Recently, there has been much research on processes that are mostly random, but also have a small amount of deterministic choice; e.g., Achlioptas processes on graphs. This talk builds on the balanced allocation algorithm first described by Azar, Broder, Karlin and Upfal. Their algorithm (and its relatives) uses randomness and some choice to distribute balls into bins in a balanced way. Here we give a description of the opposite family of algorithms, with an analysis of exactly how unbalanced the distribution can become.