Rutgers Discrete Mathematics Seminar

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.