Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - April 29, 2013

Linda Casals lindac at
Mon Apr 29 08:19:58 EDT 2013


DIMACS/CCICADA Interdisciplinary Seminar Series Presents

Title: Unbalanced allocations and cost minimization

Speaker: Amanda Redlich, Rutgers University

Date: Monday, April 29, 2013 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, 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. This
talk builds on the balanced allocation algorithm first described by
Azar, Broder, Karlin and Upfal. Their algorithm (and its relatives)
uses the "power of two choices" to distribute balls into bins in a
balanced way. This balls-and-bins algorithm has many applications:
load balancing, server allocation, hashing...

Many applications of balls-and-bins algorithms come with a cost
function; the placement of each ball in a bin has an associated
cost. In these cases, an unbalanced distribution is often the cheapest
option. One approach to cost minimization is to look at the unbalanced
allocation algorithms that use randomness and choice. Here I present
these algorithms with an analysis of exactly how unbalanced the
distribution can become. Much of this talk grows out of a cost
minimization problem I worked on during an internship at Tata
Consultancy Services.

DIMACS/CCICADA Interdisciplinary Series Calendar 2013-

More information about the Dimacs-ccicada-announce mailing list