Unbalanced Allocations

Unbalanced Allocations

-
Amanda Redlich, Rutgers University
Fine Hall 224

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 is a description of the opposite family of algorithms, with an analysis of exactly how unbalanced the distribution can become.