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
Abstract:
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.