Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 27, 2012 - 4:30pm

Amanda Redlich

Rutgers University

Location

University of Pennsylvania

DRL 3C6

There is a long history of algorithms that combine some randomness and some determinism to be both efficient and effective. The "power of two choices" used in the balls-and-bins allocation algorithm of Azar, Broder, Karlin and Upfal started this area, which now ranges from Achlioptas processes on random graphs to queuing theory applications. In most applications, the goal is a low-complexity algorithm which creates a balanced distribution (with respect to maximum bin size, queue length, connectivity, etc.). Here we discuss a novel application whose goal is a low-complexity algorithm which creates an unbalanced distribution. The analysis of this algorithm uses ideas from differential equations, random walks, and some new approaches.